回溯---组合总和(III) Posted on 2021-07-01 00:00:00 2022-04-25 00:00:00 by Author 摘要 组合问题又又又来了，这次它又能变出什么花样尼，一起进来看看吧！！！！！！！ # 回溯---组合总和(III) 1. 题目描述 - 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： - 所有数字（包括目标数）都是正整数。 - 解集不能包含重复的组合。 2. 示例描述 - 示例一 - 输入：candidates = [10,1,2,7,6,1,5], target = 8 - 输出： ``` [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] ``` - 示例二 - 输入：candidates = [2,5,2,1,2], target = 5 - 输出： ``` [ [1,2,2], [5] ] ``` 3. 解题思路 - 本题又是一道组合总和问题，又是一道组合问题的扩展型题目。首先来分析本题与其他两道题目的不同点。本题与[组合总和(II)](http://www.geticsen.cn/view/articles/detail/07ecc85a-99a2-4cfa-a8ba-dd7e5cc9e796 "组合总和(II)")相比第一个不同点就是数组中会出现重复的节点。这使得最终结果集合中会出现相同的组合，而`组合总和(II)`题目要求是可以使组合中的节点出现无限次，而本题让一个节点在一个组合中只出现一次，并且组合中有相同的节点，而且最终结果集中不允许重复的组合，这就使得本题有点难度。 - 首先我拿到本题的时候，毫不犹豫的拿我自己总结的五步法去实现(按照之前的 实现逻辑处理的)，但是在leetCode进行AC时，发现会出现相同的组合，就是最终集合中有相同的组合，在实现过程中，没有处理去重的逻辑。其实我自己也弄了好半天，发现自己还是不能在递归回溯中达到去重的效果，所以自己参考公众号`代码随想录`carl哥的本题的算法题解。然后慢慢弄明白其中的精髓。以下是我个人的理解，大家可以看看carl哥的这道题目的题解，自己慢慢理解。 - 首先所给的数组集合中有重复的值，题目中规定一个组合中 可以出现相同的值，但是每个节点只能用一次(这里值与节点不是一个意思，值代表组合中可以出现相同的值，而节点就是数组每个的元素)。这里用之前的逻辑处理这部分是没有问题的。主要问题就出现在，如果在本次节点递归回溯完成后，需要执行本次集合中的其他元素的递归回溯逻辑了，但是在本次集合中下次执行的元素与本次执行元素是相同的 ，那么就大概率会出现有重复的组合。怎么说尼？这里举个栗子，nums=[1,1,7],target=8。首先第一次递归回溯集合为[1,1,7]，这里记录值为1,下次在本层基础上继续下层递归，那时递归的集合为[1,7],此时选中1，继续执行第二层递归的下层递归，此时递归的集合为[7]，那么此时组合中的值大于target，结束第三层递归，回溯道第二层的初始位置，那么组合中元素为[1]，此时第二层的循环集合为[1,7],这时执行除`元素1`外的其他集合元素，那只有7了，此时到达第三层集合满足要求，即组合为[1,7],sum==target推出第三层递归，并且第二层递归的集合遍历也已经结束(因为元素 7为集合的末尾了，所以推退出本层循环)。此时递归回溯到第一次递归循环的位置，此时组合中为[]，剩余的集合为[1,7]，然后执行该集合下的递归回溯算法 ，毫不疑问，最终会出现一个组合为[1,7],这样最终集合会出现两个相同的组合[1,7]了，就达不到去重的效果。 - 所以为了达到去重的效果，我们应该在给数组的每一个元素设立一个标志位，判断每次递归的时候，看该元素在本层遍历集合中之前是否出现过，如果出现过，那么本层的本次递归就不用处理了，因为本层的集合中之前有元素以及处理了，在处理就会出现相同的组合了，达不到去重的效果。然后每一层的处理逻辑类似，于是最后的集合中就会没有相同的z组合，就能达到去重的效果。以上是我个人的理解，各位彦祖与亦菲可以自己试着理解，以下是实现逻辑，大家按着题解与代码自己思考一下下。 4. 代码示例 ```java //最终结果集合 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { //给数组每一个元素设置一个标志位 boolean used[] = new boolean[candidates.length]; //初始值为false //代表每个元素之前没有被用过 for (int i = 0; i < used.length; i++) { used[i] = false; } //对数组元素进行排序 //这里排序的目的是为了之后容易判断在到本层递归时，该节点之前是否使用过 Arrays.sort(candidates); //调用自己写的递归回溯算法实现 trackBack(candidates, 0, 0, target, new ArrayList<>(), used); return result; } public void trackBack(int[] candidates, int index, int sum, int target, List<Integer> tempResult, boolean[] used) { //递归出口，满足条件的情况下 if (target == sum) { result.add(new ArrayList<>(tempResult)); return; } //已经不满足条件时的递归出口 if (sum > target || index >= candidates.length) return; //每层中的每个节点都有递归回溯遍历 for (int i = index; i < candidates.length; i++) { //这一步就是去重的精华所在 //判断之前是否有相同的节点，并且之前是否被使用过，如果之前使用过，并且之前节点与本层本次递归的元素相同，那么该元素就不用递归回溯的处理 //继续执行本层其他节点的相关逻辑 //这里为什么used[i-1]==false，就说明之前使用过了尼，因为初始化的时候我们定义每个元素为false, //并且这里时递归回溯的逻辑里，到达这一步说明上一次回溯已经结束了，就说明该元素之前的节点要回溯到初始时状态 //而初始时状态就为false,那么就能说明为什么used[i-1]==false了。 if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue; //记录本层本次节点递归时的值 used[i] = true; sum += candidates[i]; tempResult.add(candidates[i]); //继续调用本层本次节点的下一层递归逻辑 trackBack(candidates, i + 1, sum, target, tempResult, used); //回溯到初始状态，以便于本层其他元素的回溯递归操作 used[i] = false; sum = sum - candidates[i]; tempResult.remove(tempResult.size() - 1); } } ```
{{ item.content }}
{{ child.content }}