# 0040. 组合总和 II

### 题目地址(40. 组合总和 II)

<https://leetcode-cn.com/problems/combination-sum-ii/>

### 题目描述

```
给定一个数组 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://p.ipic.vip/uivnzh.jpg)

> 每一层灰色的部分，表示当前有哪些节点是可以选择的， 红色部分则是选择路径。1，2，3，4，5，6 则分别表示我们的 6 个子集。

> 图是 [78.subsets](/leetcode-solution/medium/78.subsets.md)，都差不多，仅做参考。

通用写法的具体代码见下方代码区。

对于一个数组 \[1,1,3]，任选其中两项，其组合有 3 种。分别是 (1,3), (1,1) 和 (1,3)。实际上，我们可以将两个 (1,3) 看成一样的（部分题目不能看成一样的，但本题必须看成一样的）。我们可以排序的方式进行剪枝处理。即先对数组进行一次排序，不妨进行一次升序排序。接下来我们需要修改 backrack 函数内部。先来看出修改之前的代码：

```py
 if target == 0:
    res.append(path.copy())
else:
    for i in range(begin, size):
        left_num = target - candidates[i]
        if left_num < 0:
            break
        path.append(candidates[i])
        self._find_path(candidates, path, res, left_num, i+1, size)
        path.pop()
```

这里的逻辑一句话概括其实就是 **分别尝试选择 candidates\[i] 和不选择 candidates\[i]**。对应上面的 \[1,1,3]任选两项的例子就是：

* 选择第一个 1，不选择第二个 1，选择 3。就是 \[1,3]
* 不选择第一个 1，选择第二个 1，选择 3。就是 \[1,3]
* ...

那么如果将代码改为：

```py

 if target == 0:
    res.append(path.copy())
else:
    for i in range(begin, size):
        # 增加下面一行代码
        if i > begin and candidates[i] == candidate[i - 1]: continue
        left_num = target - candidates[i]
        if left_num < 0:
            break
        path.append(candidates[i])
        self._find_path(candidates, path, res, left_num, i+1, size)
        path.pop()
```

经过这样的处理，重复的都会被消除。

### 关键点解析

* 回溯法
* backtrack 解题公式

### 代码

* 语言支持: Javascript, Python3, CPP

```js
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可能有重复
    // 代码表示就是下面这一行。注意 i > start 这一条件
    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:

```python
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()
```

CPP Code:

```cpp
class Solution {
    vector<vector<int>> ans;
    void backtrack(vector<int> &A, int target, int start, vector<int> &path) {
        if (!target) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i < A.size() && target >= A[i]; ++i) {
            if (i != start && A[i] == A[i - 1]) continue;
            path.push_back(A[i]);
            dfs(A, target - A[i], i + 1, path);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& A, int target) {
        sort(A.begin(), A.end());
        vector<int> path;
        backtrack(A, target, 0, path);
        return ans;
    }
};
```

### 相关题目

* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [46.permutations](/leetcode-solution/medium/46.permutations.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [78.subsets](/leetcode-solution/medium/78.subsets.md)
* [90.subsets-ii](/leetcode-solution/medium/90.subsets-ii.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)
* [131.palindrome-partitioning](/leetcode-solution/medium/131.palindrome-partitioning.md)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/vyqn2v.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/40.combination-sum-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.