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++开始起作用。

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

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

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