# 组合总和II

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#中等) [![](https://img.shields.io/static/v1?label=\&message=LeetCode\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#leetcode) [![](https://img.shields.io/static/v1?label=\&message=%E9%80%92%E5%BD%92\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#递归) [![](https://img.shields.io/static/v1?label=\&message=LeetCode%20Hot%20100\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#leetcode-hot-100)

> [40. 组合总和 II - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum-ii/)

**问题简述**

```
给定一个候选人编号的集合 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 
```

**思路**

* 递归+回溯模板；
* 代码细节：
  * 每个数字只用一次；
  * 组合去重；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        ret = []

        def dfs(s, start, tmp):

            if s >= target:
                if s == target:
                    ret.append(tmp[:])
                return
            
            for i in range(start, len(candidates)):
                # 注意这里是 i > start（每个数字取一次），而不是 i > 0（每种数字取一次）
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                tmp.append(candidates[i])
                dfs(s + candidates[i], i + 1, tmp)  # i + 1 表示下一个开始取，即每个数字只使用一次
                tmp.pop()

        candidates.sort()  # 排序
        dfs(0, 0, [])
        return ret
```

</details>

**相关问题**

* [39. 组合总和 - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum/)