回溯---组合总和(II) Posted on 2021-06-30 00:00:00 2021-06-30 00:00:00 by Author 摘要 组合问题又又来了,本题又是一道组合的题目,与前面一道题目非常类似,but如果两个题目一起理解了,你会收获颇多哦(一起进来看看吧!!!!) # 回溯---组合总和(II) 1. 题目描述 - 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 - 提示: 1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500 2. 示例描述 - 示例一 - 输入:candidates = [2,3,6,7], target = 7 - 输出: ``` [ [7], [2,2,3] ] ``` - 示例二 - 输入:candidates = [2,3,5], target = 8 - 输出: ``` [ [2,2,2,2], [2,3,3], [3,5] ] ``` 3. 解题思路 - 本题同样还是一道递归回溯的算法,前面出现也有类似的一道题目,前面的[回溯---总和(I)](http://www.geticsen.cn/view/articles/detail/d54128be-7cde-4ddf-b421-954e52993adc "回溯---总和(I)")这篇文章和本题非常类似,但是题目要求有点不一样,这两道题目要求两点不一样,其一就是,上一篇文章给定的集合是特定的一到九的集合,而本题所给的集合就是随机的数组。第二点不一样的地方就是上一篇文章的每一组集合中不能出现相同的集合中的元素,而 本道题目的要求是,每组的集合中可以出现相同的元素。这就是 本题的不一样的地方,其余的题目要求都是一样的。 - 如果各位亦菲与彦祖能够明白递归回溯的思想与每一层都在做什么事的时候,并且理解了上道题目的解法,那么对于本题,那就是信手捏来啊。这里我还是按照我自己总结的回溯递归五步法来解决。这里我主要讲一下在与上道题目 不同地方的逻辑。首先对于递归循环的 集合不一样,那在本题中,递归循环的集合改成对所给的数组进行遍历就行了,这木有什么难度。下面就具体看看第二个不一样的地方,这个地方有时候看的人很迷,但是如果能够理解递归回溯思想的整体过程,那么个人而言就没有什么难度了。首先我们到底一个节点后,前三步还是和上一道题目逻辑类似。本道题目的难点就在第四步,调用自身的回溯递归函数这里。以前我们做法就是到达本层,调用递归函数的时候,是调用除去本层节点外中集合的其他节点的递归函数。这样就能排除一个组合中不会出现本层节点的值。而本道题目要求是集合中可以出现相同的节点,那么我们举一反三,如果不出现相同的节点,那么我们下次递归的时候就把本次的节点从集合中去掉即可。如果可以出现相同的节点,那么我们在下次进行递归调用的时候,本次的节点,就可以出现在下次遍历的集合中,那么就会出现可以允许相同的节点出现在同一个集合中。这就满足的题目要求,同时我们也可以通过比较可以得出什么时候使用第一种方法,什么时候使用第二种方法了。 - 各位彦祖和亦菲可以仔细品味一下,个人的理解就是这些,下面就是本题的具体实现逻辑,大家可以把这两道题拿出来相互比较一下,然后在总结一下,我相信你会收获颇多!!!! 4. 代码示例 ```java //最终结果集合 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { //调用我们自己写的递归回溯函数 trackBack(candidates, 0, target, new ArrayList<>(), 0); return result; } public void trackBack(int[] candidates, int index, int target, List<Integer> tempResult, int sum) { //递归出口的条件 if (sum == target) { result.add(new ArrayList<>(tempResult)); return; } //不满足条件的递归出口 if (index >= candidates.length || sum > target) return; //这里遍历的集合变成循环遍历数组了 for (int i = index; i < candidates.length; i++) { //记录本次递归时的值 sum += candidates[i]; tempResult.add(candidates[i]); //这里允许集合出现相同的节点,就在与调用递归函数的时候,index没有加一 //也就是下次递的时候,下次遍历的集合也包含本次的节点,这样就能够保证一个组合 //中可以出现出现相同的节点了, trackBack(candidates, i, target, tempResult, sum); //下面就是在递归回退的时候,移除本层的节点,保证该层其余集合的节点在操作时,不受影响 sum = sum - candidates[i]; tempResult.remove(tempResult.size() - 1); } } ```
{{ item.content }}
{{ child.content }}