对回溯算法的理解
=凌晨= 人气:0最近一直在刷leetcode的回溯算法的题目，想趁着熟悉记录一下自己的理解。
回溯算法虽然是暴力搜索，但是其实是有方法的暴力搜索。目前做的题目包括组合总和I，II，全排列I，II，组合，子集I，II。其中组合总和I中
这里的特点就是数组中的值都可以反复选取。因此再画遍历树的时候，每次都会重新遍历。然而解集需要去重，因此需要减枝操作。
对于这种求和等于目标值的，首先要解决遍历时候的深度问题。所以技巧一就是在递归的时候，将target换成target-candidates[j]。如下所示
1 private static void tracback(int len, int index, int[] candidates, int target, List<List<Integer>> ans, List<Integer> path) {
2
3 if(target==0){
4 ans.add(new ArrayList<>(path));
5 return;
6 }
7
8 for (int j = index; j < len; j++) {
9 if(target-candidates[j]<0){
10 return;
11 }
12 path.add(candidates[j]);
13 tracback(len,j,candidates,target-candidates[j],ans,path);
14 path.remove(path.size()-1);
15 }
16 }
返回条件就是target==0即找到了路径。另外因为每次遍历到下一个深度的节点的时候，都是数组内的元素都有可能成为选择项，所以在递归的时候，j并不需要加1.。
接下来就是去重的问题，首先去重的前提就是对数组就行排序。
1 public static List<List<Integer>> combinationSum(int[] candidates, int target) {
2 List<List<Integer>> ans = new ArrayList<>();
3 List<Integer> path = new ArrayList<>();
4 Arrays.sort(candidates);
5 int len = candidates.length;
6 tracback(len,0,candidates,target,ans,path);
7 return ans;
8 }
当目标值减去当前节点的值的时候小于0的时候，就代表着不用进行遍历。另外需要注意的是第四行代码。直接ans.add(path)则结果会全部为[]。原因是因为最后每次都回溯了。所以当需要存储的时候，需要对其进行复制。
组合总和II
这道题与前一道的区别也很明显。在这题中。主要难点是再大剪枝的情况下还有一个小剪枝。引用这位大佬的解释
在排列问题中。
这里我们的想法是在之前代码模板不变的情况下，我们加入了替换顺序来使每种情况都有
1 public static void tracback(List<List<Integer>> ans, List<Integer> path, int[] nums,int depth) {
2 if(path.size()==nums.length){
3 ans.add(new ArrayList<>(path));
4 return;
5 }
6
7 for (int i = depth; i < nums.length; i++) {
8 path.add(nums[i]);
9 int temp = nums[i];
10 nums[i] = nums[depth];
11
12 nums[depth] = temp;
13 tracback(ans, path, nums,depth+1);
14 int temp1 = nums[i];
15 nums[i] = nums[depth];
16 nums[depth] = temp1;
17 path.remove(path.size()-1);
18 }
19 }
即变换前1-2-3.在回溯的时候还能满足1-2.
另外就是可以引用一个boolean类型的used数组来代表是不是已经使用过了。这样for循环的起点就一直是0了。
1 // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
2 for (int i = 0; i < len; i++) {
3 if (!used[i]) {
4 path.add(nums[i]);
5 used[i] = true;
6
7 dfs(nums, len, depth + 1, path, used, res);
8 // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
9 used[i] = false;
10 path.remove(path.size() - 1);
11 }
12 }
13
14 作者：liweiwei1419
15 链接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
16 来源：力扣（LeetCode）
17 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
在子集问题中
需要注意的是这种没有重复值的需要在每个节点都存储结果，所以不需要返回。
1 public static void tranback(int[] nums, List<Integer> path, List<List<Integer>> ans, int start,int i){
2 // if (path.size() == i){
3 ans.add(new ArrayList<>(path));
4 // return;
5 //}
6
7 for (int j = start; j < nums.length; j++) {
8 path.add(nums[j]);
9 tranback(nums,path,ans,j+1,i);
10 path.remove(path.size()-1);
11 // tranback(nums,path,ans,j+1,i);
12 }
13 }
另外j+1便可以实现去重。对于子集II数组重复的情况下去重就按照数组总和II那样剪枝处理即可。
加载全部内容