简析回溯算法

本文主要是介绍简析回溯算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

回溯算法

非常好用的一种算法。通俗的来说就是将所有的数据转化为树形结构，依次往下走，走不下去可以退回去的一种算法。

例子1 数组返回不同排列的值

给定一个可重复的数组，按照不同的顺序组合成不同的集合，有多少种。分别是什么？

int scores2[] = new int[]{1,2,3};

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

int scores2[] = new int[]{1,3,3};

[1, 3, 3]
[3, 1, 3]
[3, 3, 1]

这里使用回溯方法，返回一个list的list集合，参数是一个数组。
定义第一个变量 visited 用于保存所有的可能是否走完或者说是当前是步骤做的数字，和参数中的数组长度一样，用来记录那些步骤走了，那些没走。
result 结果集
tmp 满足条件的值
首先将数组排序

 public static List<List<Integer>> getCombination(int[] nums) {
	        int[] visited = new int[nums.length];
	        ArrayList<List<Integer>> result = new ArrayList<>();
	        ArrayList<Integer> tmp = new ArrayList<>();
	        Arrays.sort(nums);//排序
	        backtrack(result, tmp, nums, visited);
	        return result;
	    }

backtrack就是回溯的意思，传入结果集，满足条件的值，数组，和步骤记录

public void backtrack(ArrayList<List<Integer>> result, ArrayList<Integer> tmp, int[] nums, int[] visited) {
	        if(tmp.size() == nums.length){
	            result.add(new ArrayList<>(tmp));
	            return;
	        } 
	        for(int i = 0; i < nums.length; i++){
	            if (visited[i] == 1) continue;           
	            if(i > 0 && nums[i-1] == nums[i] && visited[i-1] != 0) continue;//剪枝
	            tmp.add(nums[i]);
	            visited[i] = 1;
	            backtrack(result, tmp, nums, visited);
	            tmp.remove(tmp.size()-1);
	            visited[i] = 0;
	        }
	    }

      if(tmp.size() == nums.length){
          result.add(new ArrayList<>(tmp));
          return;
      }

如果值满足条件那么就会加入到结果中，直接跳出循环。

遍历条件数组，如果当前这步骤走了，则跳出当前。
如果当前值和上一个值相等，且上一个值已经走了，则跳出当前。
加入数组中，当前步骤记录已经走了，迭代当前数。
减去加入的想，将当前步骤变更为未走。

  for(int i = 0; i < nums.length; i++){
	            if (visited[i] == 1) continue;           
	            if(i > 0 && nums[i-1] == nums[i] && visited[i-1] != 0) continue;//剪枝
	            tmp.add(nums[i]);
	            visited[i] = 1;
	            backtrack(result, tmp, nums, visited);
	            tmp.remove(tmp.size()-1);
	            visited[i] = 0;
	        }

这篇关于简析回溯算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！