0040. 组合总和 II · ttttt

# 0040. 组合总和 II ## 题目地址(40. 组合总和 II) <https://leetcode-cn.com/problems/combination-sum-ii/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ] ``` ``` ## 前置知识 - 回溯法 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路这道题目是求集合，并不是`求极值`，因此动态规划不是特别切合，因此我们需要考虑别的方法。这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的 [通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，这里的所有的解法使用通用方法解答。除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。我们先来看下通用解法的解题思路，我画了一张图： ![](https://img.kancloud.cn/46/ec/46ec3382e572355e2109c47284e37e4b_1341x1080.jpg) > 图是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，仅做参考。通用写法的具体代码见下方代码区。 ## 关键点解析 - 回溯法 - backtrack 解题公式 ## 代码 - 语言支持: Javascript，Python3 ``` <pre class="calibre18">``` function backtrack(list, tempList, nums, remain, start) { if (remain < 0) return; else if (remain === 0) return list.push([...tempList]); for (let i = start; i < nums.length; i++) { // 和39.combination-sum 的其中一个区别就是这道题candidates可能有重复 // 代码表示就是下面这一行 if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.push(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i + 1); // i + 1代表不可以重复利用， i 代表数字可以重复使用 tempList.pop(); } } /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 = function(candidates, target) { const list = []; backtrack(list, [], candidates.sort((a, b) => a - b), target, 0); return list; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: """ 与39题的区别是不能重用元素，而元素可能有重复；不能重用好解决，回溯的index往下一个就行；元素可能有重复，就让结果的去重麻烦一些； """ size = len(candidates) if size == 0: return [] # 还是先排序，主要是方便去重 candidates.sort() path = [] res = [] self._find_path(candidates, path, res, target, 0, size) return res def _find_path(self, candidates, path, res, target, begin, size): if target == 0: res.append(path.copy()) else: for i in range(begin, size): left_num = target - candidates[i] if left_num < 0: break # 如果存在重复的元素，前一个元素已经遍历了后一个元素与之后元素组合的所有可能 if i > begin and candidates[i] == candidates[i-1]: continue path.append(candidates[i]) # 开始的 index 往后移了一格 self._find_path(candidates, path, res, left_num, i+1, size) path.pop() ``` ``` ## 相关题目 - [39.combination-sum](39.combination-sum.html) - [46.permutations](46.permutations.html) - [47.permutations-ii](47.permutations-ii.html) - [78.subsets](78.subsets.html) - [90.subsets-ii](90.subsets-ii.html) - [113.path-sum-ii](113.path-sum-ii.html) - [131.palindrome-partitioning](131.palindrome-partitioning.html)