最近一直在刷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那样剪枝处理即可。

版权声明：本文为lingchenstudy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lingchenstudy/p/14520346.html