个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰这里提前祝大家周末快乐可能还有大部分现在还在加班呢今天又到了我们的每日刷题环节让我们一起看看吧。摘要本文讲解了两道组合总和问题的回溯解法。39题要求从无重复元素的数组中找出和为target的组合元素可重复使用通过排序剪枝优化递归过程。40题变式要求处理含重复元素的数组且每个元素只能使用一次通过排序树层去重istart candidates[i]candidates[i-1]避免重复组合。两题都采用回溯框架关键区别在于递归参数传递i/i1和去重逻辑。文章通过示例详细演示了递归树构建过程并提供了Java实现代码强调排序对剪枝和去重的重要性。题目背景39.组合总和给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。示例 1输入candidates [2,3,6,7], target 7输出[[2,2,3],[7]]解释2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。示例 2输入:candidates [2,3,5], target 8输出:[[2,2,2,2],[2,3,3],[3,5]]示例 3输入:candidates [2], target 1输出:[]提示1 candidates.length 302 candidates[i] 40candidates的所有元素互不相同1 target 40题目解析拿到这个题目我们很容易联想到前面我们在二叉树学习的时候做过的给定一个目标值找出总和等于目标值的集合还有77题的组合问题这其实都是很相关的问题就是在原来的基础上进行的拓展我们这里完全就是利用组合的思路仅仅是加上了总和的问题所以我们主要侧重研究总和问题其他的思路我们都已经很熟悉了。总和计算我们先明确题目中给的需求数组是无重复元素的但是选取的时候可以多次使用同一元素结果集合不能重复我们的思路主要围绕这个要求进行拓展无重复元素不必多说其实我们拿到的大多数题目的数组元素都是无重复的没什么特殊的具体这里为什么要强调因为下面还有一个变种题目可以思考一下。然后就是选取的时候可以多次使用同一元素如果要实现这个那么就是我们77题组合的核心思路找出所有的组合但还是有点差异就是同一元素可以重复无非就是多了几种情况然后在单层递归的时候加上一个计算总和的逻辑后序还可以根据这个总和对代码进行相应的剪枝优化。至于结果集合不能重复我们在递归过程中就已经确保了。本题搜索的过程抽象成树形结构如下注意图中叶子节点的返回条件因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回递归函数参数这里依然是定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。这两个变量可以作为函数参数传入首先是题目中给出的参数集合candidates, 和目标值target。此外我还定义了int型的sum变量来统计单一结果path里的总和其实这个sum也可以不用用target做相应的减法就可以了最后如何target0就说明找到符合的结果了但为了代码逻辑清晰我依然用了sum。本题还需要startIndex来控制for循环的起始位置对于组合问题什么时候需要startIndex呢举过例子如果是一个集合来求组合的话就需要startIndex如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex注意以上只是说求组合的情况如果是排列问题又是另一套分析的套路讲解排列的时候会重点介绍。递归终止条件在如下树形结构中从叶子节点可以清晰看到终止只有两种情况sum大于target和sum等于target。sum等于target的时候需要收集结果代码如下if (sum target) { return; } if (sum target) { result.push_back(path); return; }单层搜索的逻辑单层for循环依然是从startIndex开始搜索candidates集合。剪枝优化在这个树形结构中以及上面的版本一的代码大家可以看到对于sum已经大于target的情况其实是依然进入了下一层递归只是下一层递归结束判断的时候会判断sum target的话就返回。其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。那么可以在for循环的搜索范围上做做文章了。对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。如图我们这里注意到是直接跳过那么说明用的就是break其实这里也隐含了一个重要的条件那么就是数组必须是有序的只有这样才可以直接跳过后面的如果后面的元素还有比当前判断元素小的那么这个if条件判断就不一定成立了如果不想排序就只能用continue了只能跳过当前循环不能直接break核心原因break 需要有序性java if (sum candidates[i] target) break; // 这里用了 breakbreak的含义终止整个for循环后面的元素不再检查。这要求数组必须满足如果当前元素过大后面的元素更大或相等这样跳过后面的元素才是安全的。为什么未排序时 break 会出错假设 candidates [6, 3, 2, 7]未排序target 7 java 排序后: [2, 3, 6, 7] ✅ 可以使用 break 未排序: [6, 3, 2, 7] ❌ 不能使用 break实例分析java candidates [2, 3, 6, 7] target 7递归树执行过程text 初始状态: result[], current[], remaining7, start0第一层递归i0, 数字21. 选择2: current[2], remaining5 ├─ 第二层递归i0, 数字2 │ ├─ 选择2: current[2,2], remaining3 │ │ ├─ 第三层递归i0, 数字2 │ │ │ ├─ 选择2: current[2,2,2], remaining1 │ │ │ │ ├─ 第四层递归 │ │ │ │ │ ├─ i0: 21? break (剪枝) │ │ │ │ │ └─ 回溯: current[2,2,2] │ │ │ ├─ i1: 31? break │ │ │ └─ 回溯: current[2,2] │ │ ├─ i1: 选择3: current[2,2,3], remaining0 ✓ 找到组合! │ │ │ └─ result.add([2,2,3]), 回溯: current[2,2] │ │ ├─ i2: 63? break │ │ └─ 回溯: current[2] │ ├─ i1: 选择3: current[2,3], remaining2 │ │ ├─ 第三层递归i1, 数字3 │ │ │ ├─ 选择3: current[2,3,3], remaining-1 (无效) │ │ │ │ └─ 回溯: current[2,3] │ │ │ ├─ 选择5: candidates[2]5? 6? 实际是6 │ │ │ │ └─ 3697? continue │ │ │ └─ 回溯: current[2] │ │ ├─ i2: 选择6: current[2,6], remaining-1 (无效) │ │ └─ 回溯: current[2] │ ├─ i2: 选择6: current[2,6], remaining-1 │ └─ 回溯: current[] │ ├─ i1: 选择3: current[3], remaining4 │ ├─ 第二层递归i1, 数字3 │ │ ├─ 选择3: current[3,3], remaining1 │ │ │ ├─ i1: 31? break │ │ │ └─ 回溯: current[3] │ │ ├─ 选择6: current[3,6], remaining-2 (无效) │ │ └─ 回溯: current[] │ │ │ └─ 回溯: current[] │ └─ i2: 选择6: current[6], remaining1 ├─ 第二层递归i2, 数字6 │ ├─ i2: 61? break │ └─ 回溯: current[] └─ 回溯: current[]### 第一层递归i3, 数字7 选择7: current[7], remaining0 ✓ 找到组合! └─ result.add([7]), 回溯: current[] text ## 最终结果 java result [[2,2,3], [7]]这里测试用例递归过程中用的是剩余的总和其实跟我们自己计算总和是一样的只不过之逆着来本质都是一样的。题目答案剪枝优化 class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger res new ArrayList(); Arrays.sort(candidates); // 先进行排序 backtracking(res, new ArrayList(), candidates, target, 0, 0); return res; } public void backtracking(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int idx) { // 找到了数字和为 target 的组合 if (sum target) { res.add(new ArrayList(path)); return; } for (int i idx; i candidates.length; i) { // 如果 sum candidates[i] target 就终止遍历 if (sum candidates[i] target) break; path.add(candidates[i]); backtracking(res, path, candidates, target, sum candidates[i], i); path.remove(path.size() - 1); // 回溯移除路径 path 最后一个元素 } } }既然这题已经拿下那么我们直接顺势把这题的变式也顺便搞定题目背景40.组合总和Ⅱ给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。注意解集不能包含重复的组合。示例 1:输入:candidates [10,1,2,7,6,1,5], target 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]]示例 2:输入:candidates [2,5,2,1,2], target 5,输出:[[1,2,2],[5]]提示:1 candidates.length 1001 candidates[i] 501 target 30题目分析由于这道题就是上面题目的变式这里我们直接找题目中不一样的需求这里是数组中有重复元素选取的时候每个元素在组合中只能使用一次结果集不能重复这么一看整体的思路其实就改变了当然我们只要解决了这改变的两个条件这道题就能迎刃而解了。去重分析在回溯算法的树形结构中纵向树枝一条路径从上到下的选择代表递归深度横向树层同一层级的多个选择代表for循环遍历text 根节点 / | \ / | \ / | \ 选择2 选择3 选择6 ← 同一树层横向 | | | ... ... ... | | | 结果 结果 结果 ← 不同树枝纵向java // 以40题为例candidates [1,1,2], target 3 [] / | \ 选1(第一个) 选1(第二个) 选2 | | | [1] [1] [2] / \ / \ / \ 选1(2nd) 选2 选1(2nd) 选2 选1 选... | | | | [1,1] [1,2] [1,1] [1,2] | | | | ❌ ✅ ❌ ✅问题[1,2]出现了两次一个用第一个1一个用第二个1维度方向判断条件典型题目目的同一树层横向for循环i start nums[i] nums[i-1]40题、90题避免重复组合同一树枝纵向递归深度used[i]数组标记46题、47题避免重复使用元素核心理解树层去重保证同一层不会选择相同的值避免产生相同的组合树枝不去重允许在一条路径上使用相同值如果值本身重复这就是去重的精髓了代码分析1. 递归参数i vs i1java // 39题可以重复使用当前元素 backtrack(res, path, candidates, target, sum candidates[i], i); // ↑ // 传递 i不是 i1 // 40题每个元素只能使用一次 backtrack(res, path, candidates, target, sum candidates[i], i 1); // ↑ // 传递 i1不能重复使用 示例说明 java // 39题candidates[2,3,6,7], target7 // 选择2后仍然可以从索引0开始选择 [2] → 可以继续选2 → [2,2] → 可以继续选2 → [2,2,2]... // 40题candidates[1,1,2,5,6,7,10], target8 // 选择第一个1后下次从下一个索引开始 [1] → 只能选索引1及之后的元素不能重复选索引0的12. 去重逻辑java // 40题需要去重因为candidates可能有重复元素 if (i start candidates[i] candidates[i - 1]) { continue; // 跳过重复元素避免产生相同组合 }为什么需要去重java // 输入: candidates [1,1,2], target 3 // 如果不加去重逻辑会得到 [ [1,2], // 使用第一个1 [1,2] // 使用第二个1重复了 ] // 加上去重后 [ [1,2] // 只有一个 ]3. 剪枝条件相同但意义不同java // 两道题都使用了相同的剪枝 for (int i start; i candidates.length sum candidates[i] target; i) // 但作用略有不同 // 39题因为可以重复使用剪枝更重要避免无限递归 // 40题剪枝同样重要但深度受限于元素个数剩下的逻辑就是回溯了没什么区别题目答案class Solution { public ListListInteger combinationSum2(int[] candidates, int target) { ListListInteger res new ArrayList(); Arrays.sort(candidates); // 必须排序便于去重 backtrack(res, new ArrayList(), candidates, target, 0, 0); return res; } private void backtrack(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int start) { if (sum target) { res.add(new ArrayList(path)); return; } for (int i start; i candidates.length sum candidates[i] target; i) { // 关键1去重 - 跳过同一层重复的元素 if (i start candidates[i] candidates[i - 1]) { continue; } path.add(candidates[i]); // 关键2传递 i1每个元素只能使用一次 backtrack(res, path, candidates, target, sum candidates[i], i 1); path.remove(path.size() - 1); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】39.组合总和40.组合总和Ⅱ
发布时间：2026/6/6 16:32:14
个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰这里提前祝大家周末快乐可能还有大部分现在还在加班呢今天又到了我们的每日刷题环节让我们一起看看吧。摘要本文讲解了两道组合总和问题的回溯解法。39题要求从无重复元素的数组中找出和为target的组合元素可重复使用通过排序剪枝优化递归过程。40题变式要求处理含重复元素的数组且每个元素只能使用一次通过排序树层去重istart candidates[i]candidates[i-1]避免重复组合。两题都采用回溯框架关键区别在于递归参数传递i/i1和去重逻辑。文章通过示例详细演示了递归树构建过程并提供了Java实现代码强调排序对剪枝和去重的重要性。题目背景39.组合总和给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。示例 1输入candidates [2,3,6,7], target 7输出[[2,2,3],[7]]解释2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。示例 2输入:candidates [2,3,5], target 8输出:[[2,2,2,2],[2,3,3],[3,5]]示例 3输入:candidates [2], target 1输出:[]提示1 candidates.length 302 candidates[i] 40candidates的所有元素互不相同1 target 40题目解析拿到这个题目我们很容易联想到前面我们在二叉树学习的时候做过的给定一个目标值找出总和等于目标值的集合还有77题的组合问题这其实都是很相关的问题就是在原来的基础上进行的拓展我们这里完全就是利用组合的思路仅仅是加上了总和的问题所以我们主要侧重研究总和问题其他的思路我们都已经很熟悉了。总和计算我们先明确题目中给的需求数组是无重复元素的但是选取的时候可以多次使用同一元素结果集合不能重复我们的思路主要围绕这个要求进行拓展无重复元素不必多说其实我们拿到的大多数题目的数组元素都是无重复的没什么特殊的具体这里为什么要强调因为下面还有一个变种题目可以思考一下。然后就是选取的时候可以多次使用同一元素如果要实现这个那么就是我们77题组合的核心思路找出所有的组合但还是有点差异就是同一元素可以重复无非就是多了几种情况然后在单层递归的时候加上一个计算总和的逻辑后序还可以根据这个总和对代码进行相应的剪枝优化。至于结果集合不能重复我们在递归过程中就已经确保了。本题搜索的过程抽象成树形结构如下注意图中叶子节点的返回条件因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回递归函数参数这里依然是定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。这两个变量可以作为函数参数传入首先是题目中给出的参数集合candidates, 和目标值target。此外我还定义了int型的sum变量来统计单一结果path里的总和其实这个sum也可以不用用target做相应的减法就可以了最后如何target0就说明找到符合的结果了但为了代码逻辑清晰我依然用了sum。本题还需要startIndex来控制for循环的起始位置对于组合问题什么时候需要startIndex呢举过例子如果是一个集合来求组合的话就需要startIndex如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex注意以上只是说求组合的情况如果是排列问题又是另一套分析的套路讲解排列的时候会重点介绍。递归终止条件在如下树形结构中从叶子节点可以清晰看到终止只有两种情况sum大于target和sum等于target。sum等于target的时候需要收集结果代码如下if (sum target) { return; } if (sum target) { result.push_back(path); return; }单层搜索的逻辑单层for循环依然是从startIndex开始搜索candidates集合。剪枝优化在这个树形结构中以及上面的版本一的代码大家可以看到对于sum已经大于target的情况其实是依然进入了下一层递归只是下一层递归结束判断的时候会判断sum target的话就返回。其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。那么可以在for循环的搜索范围上做做文章了。对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。如图我们这里注意到是直接跳过那么说明用的就是break其实这里也隐含了一个重要的条件那么就是数组必须是有序的只有这样才可以直接跳过后面的如果后面的元素还有比当前判断元素小的那么这个if条件判断就不一定成立了如果不想排序就只能用continue了只能跳过当前循环不能直接break核心原因break 需要有序性java if (sum candidates[i] target) break; // 这里用了 breakbreak的含义终止整个for循环后面的元素不再检查。这要求数组必须满足如果当前元素过大后面的元素更大或相等这样跳过后面的元素才是安全的。为什么未排序时 break 会出错假设 candidates [6, 3, 2, 7]未排序target 7 java 排序后: [2, 3, 6, 7] ✅ 可以使用 break 未排序: [6, 3, 2, 7] ❌ 不能使用 break实例分析java candidates [2, 3, 6, 7] target 7递归树执行过程text 初始状态: result[], current[], remaining7, start0第一层递归i0, 数字21. 选择2: current[2], remaining5 ├─ 第二层递归i0, 数字2 │ ├─ 选择2: current[2,2], remaining3 │ │ ├─ 第三层递归i0, 数字2 │ │ │ ├─ 选择2: current[2,2,2], remaining1 │ │ │ │ ├─ 第四层递归 │ │ │ │ │ ├─ i0: 21? break (剪枝) │ │ │ │ │ └─ 回溯: current[2,2,2] │ │ │ ├─ i1: 31? break │ │ │ └─ 回溯: current[2,2] │ │ ├─ i1: 选择3: current[2,2,3], remaining0 ✓ 找到组合! │ │ │ └─ result.add([2,2,3]), 回溯: current[2,2] │ │ ├─ i2: 63? break │ │ └─ 回溯: current[2] │ ├─ i1: 选择3: current[2,3], remaining2 │ │ ├─ 第三层递归i1, 数字3 │ │ │ ├─ 选择3: current[2,3,3], remaining-1 (无效) │ │ │ │ └─ 回溯: current[2,3] │ │ │ ├─ 选择5: candidates[2]5? 6? 实际是6 │ │ │ │ └─ 3697? continue │ │ │ └─ 回溯: current[2] │ │ ├─ i2: 选择6: current[2,6], remaining-1 (无效) │ │ └─ 回溯: current[2] │ ├─ i2: 选择6: current[2,6], remaining-1 │ └─ 回溯: current[] │ ├─ i1: 选择3: current[3], remaining4 │ ├─ 第二层递归i1, 数字3 │ │ ├─ 选择3: current[3,3], remaining1 │ │ │ ├─ i1: 31? break │ │ │ └─ 回溯: current[3] │ │ ├─ 选择6: current[3,6], remaining-2 (无效) │ │ └─ 回溯: current[] │ │ │ └─ 回溯: current[] │ └─ i2: 选择6: current[6], remaining1 ├─ 第二层递归i2, 数字6 │ ├─ i2: 61? break │ └─ 回溯: current[] └─ 回溯: current[]### 第一层递归i3, 数字7 选择7: current[7], remaining0 ✓ 找到组合! └─ result.add([7]), 回溯: current[] text ## 最终结果 java result [[2,2,3], [7]]这里测试用例递归过程中用的是剩余的总和其实跟我们自己计算总和是一样的只不过之逆着来本质都是一样的。题目答案剪枝优化 class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger res new ArrayList(); Arrays.sort(candidates); // 先进行排序 backtracking(res, new ArrayList(), candidates, target, 0, 0); return res; } public void backtracking(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int idx) { // 找到了数字和为 target 的组合 if (sum target) { res.add(new ArrayList(path)); return; } for (int i idx; i candidates.length; i) { // 如果 sum candidates[i] target 就终止遍历 if (sum candidates[i] target) break; path.add(candidates[i]); backtracking(res, path, candidates, target, sum candidates[i], i); path.remove(path.size() - 1); // 回溯移除路径 path 最后一个元素 } } }既然这题已经拿下那么我们直接顺势把这题的变式也顺便搞定题目背景40.组合总和Ⅱ给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。注意解集不能包含重复的组合。示例 1:输入:candidates [10,1,2,7,6,1,5], target 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]]示例 2:输入:candidates [2,5,2,1,2], target 5,输出:[[1,2,2],[5]]提示:1 candidates.length 1001 candidates[i] 501 target 30题目分析由于这道题就是上面题目的变式这里我们直接找题目中不一样的需求这里是数组中有重复元素选取的时候每个元素在组合中只能使用一次结果集不能重复这么一看整体的思路其实就改变了当然我们只要解决了这改变的两个条件这道题就能迎刃而解了。去重分析在回溯算法的树形结构中纵向树枝一条路径从上到下的选择代表递归深度横向树层同一层级的多个选择代表for循环遍历text 根节点 / | \ / | \ / | \ 选择2 选择3 选择6 ← 同一树层横向 | | | ... ... ... | | | 结果 结果 结果 ← 不同树枝纵向java // 以40题为例candidates [1,1,2], target 3 [] / | \ 选1(第一个) 选1(第二个) 选2 | | | [1] [1] [2] / \ / \ / \ 选1(2nd) 选2 选1(2nd) 选2 选1 选... | | | | [1,1] [1,2] [1,1] [1,2] | | | | ❌ ✅ ❌ ✅问题[1,2]出现了两次一个用第一个1一个用第二个1维度方向判断条件典型题目目的同一树层横向for循环i start nums[i] nums[i-1]40题、90题避免重复组合同一树枝纵向递归深度used[i]数组标记46题、47题避免重复使用元素核心理解树层去重保证同一层不会选择相同的值避免产生相同的组合树枝不去重允许在一条路径上使用相同值如果值本身重复这就是去重的精髓了代码分析1. 递归参数i vs i1java // 39题可以重复使用当前元素 backtrack(res, path, candidates, target, sum candidates[i], i); // ↑ // 传递 i不是 i1 // 40题每个元素只能使用一次 backtrack(res, path, candidates, target, sum candidates[i], i 1); // ↑ // 传递 i1不能重复使用 示例说明 java // 39题candidates[2,3,6,7], target7 // 选择2后仍然可以从索引0开始选择 [2] → 可以继续选2 → [2,2] → 可以继续选2 → [2,2,2]... // 40题candidates[1,1,2,5,6,7,10], target8 // 选择第一个1后下次从下一个索引开始 [1] → 只能选索引1及之后的元素不能重复选索引0的12. 去重逻辑java // 40题需要去重因为candidates可能有重复元素 if (i start candidates[i] candidates[i - 1]) { continue; // 跳过重复元素避免产生相同组合 }为什么需要去重java // 输入: candidates [1,1,2], target 3 // 如果不加去重逻辑会得到 [ [1,2], // 使用第一个1 [1,2] // 使用第二个1重复了 ] // 加上去重后 [ [1,2] // 只有一个 ]3. 剪枝条件相同但意义不同java // 两道题都使用了相同的剪枝 for (int i start; i candidates.length sum candidates[i] target; i) // 但作用略有不同 // 39题因为可以重复使用剪枝更重要避免无限递归 // 40题剪枝同样重要但深度受限于元素个数剩下的逻辑就是回溯了没什么区别题目答案class Solution { public ListListInteger combinationSum2(int[] candidates, int target) { ListListInteger res new ArrayList(); Arrays.sort(candidates); // 必须排序便于去重 backtrack(res, new ArrayList(), candidates, target, 0, 0); return res; } private void backtrack(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int start) { if (sum target) { res.add(new ArrayList(path)); return; } for (int i start; i candidates.length sum candidates[i] target; i) { // 关键1去重 - 跳过同一层重复的元素 if (i start candidates[i] candidates[i - 1]) { continue; } path.add(candidates[i]); // 关键2传递 i1每个元素只能使用一次 backtrack(res, path, candidates, target, sum candidates[i], i 1); path.remove(path.size() - 1); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
