lc回溯问题

• 40.组合总和||
• • 分析
  • 代码
• 90.子集||
• • 代码
• 总结

40.组合总和||

链接直达

分析

回溯问题

回溯三步法：

• 确定回溯函数back的参数
• 回溯的终止条件
• 把握回溯的搜索过程

具体题目分析：

1. 注意解集不能有重复的组合，那么如果我们在candidates数组中曾经选过1作为组合数，那么再次遇到1的时候，一些组合就需要排除。首先需要对数组进行排序，这样就会使得所有重复数据连在一起，我们的目的是去除重复数据组合。比如【1，1，2，6】，当我们把第一个1的组合加入之后，第二个1就不要取了，也就是说应该跳过这个第二个1

2. 这里我们选择使用一个数组来区分是否遍历过重复元素 ---- > used[]

   当相邻的数据相同的时候，比如【1，1】，我们在回溯到取第二个1的时候，就通过used跳过它：问题就推到了，怎么跳过呢？

   我们将used数组设置为两种状态，考虑使用boolean数组

   当used[i - 1] == false的时候，就说明在回溯取第二个1【此时下标是i】的时候，第一个1 【i - 1】已经取过了

   当然了，你也可以设置一个为true的时候，表示取过，这里这么设置是因为初始化数组的时候默认值为false，当我们进入递归向下的状态时，需要将本此的状态设置成!used[i]，回溯的时候再反过来—>此时是false，而正好我们回溯判断是否去除重复组合也是在这，所以如果设置成false表示取过的话，就不用初始化数组为true了，省事！

3. 其他就是老套路，判断sum == target，结束本次递归，然后回溯回去

代码

class Solution {    List<List<Integer>> returnArr = new ArrayList();    List<Integer>path = new ArrayList();    public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); boolean [] used = new boolean[candidates.length]; back(candidates,target,0,0, used); return returnArr;    }    public void back(int[] candidates, int target, int sum, int startindex,boolean[] used){ if(sum == target){     returnArr.add(new ArrayList<>(path));     return ; } for(int i = startindex; i < candidates.length; i++){   if(sum + candidates[i] > target) return ;//剪支减少递归     if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false){  continue;     }     path.add(candidates[i]);     used[i] = true;     back(candidates,target,candidates[i] + sum, i+1,used);     //这里就是在回溯了     used[i] = false;     path.remove(path.size() - 1); }    }}

90.子集||

链接直达

跟90很像的，因为需要去重重复元素，所以我还是用了used

分析也是差不多的。

代码

class Solution {    public List<List<Integer>> returnArr = new ArrayList();    public List<Integer> path = new ArrayList();    public List<List<Integer>> subsetsWithDup(int[] nums) { if(nums.length == 0){     returnArr.add(path);     return returnArr; } if(nums.length == 1){     returnArr.add(new ArrayList<>(path));     path.add(nums[0]);     returnArr.add(new ArrayList<>(path));     return returnArr; } Arrays.sort(nums); boolean[] used = new boolean[nums.length]; back(nums, used, 0); return returnArr;    }    public void back(int[] nums, boolean []used, int startindex){ if(startindex == nums.length){     returnArr.add(new ArrayList<>(path));     return ; }     returnArr.add(new ArrayList<>(path));     for(int i = startindex; i < nums.length; i++){     if(i > 0 && nums[i] == nums[i - 1] && used[i - 1]==false){  continue;     }     path.add(nums[i]);     used[i] = true;     back(nums, used, i + 1);     path.remove(path.size() - 1);     used[i] = false; }    }}

总结

最近这几天看了一部分回溯的题目，有时候莫名奇妙的就把题目写出来了，心里不知道怎么说，感觉会了又好像没会。

今天突然感觉有个东西十分通透了，因为是组合，个人的理解是首先是递归进去，相当于是纵向遍历，然后就回溯出来，出来之后是横向遍历。也就是第一层i++开始起作用。

然后一些其他的限制条件就是题目不同而不同了，一种就是递归进去的时候去重，另一种是回溯出来之后去重，其实都是在加限定条件。

但是不变的应该就是回溯的这个模式了，先向下纵向遍历一遍，然后再退出来，横向遍历一遍。

算是这几天的一点总结，以后有新心得或者改变的想法再来修正吧🤣