# \[40]\[中等]\[回溯] 组合总和 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]
]
```

## 题目描述

与[\[39\]\[中等\]\[回溯\] 组合总和](/garnet/suan-fa/hui-su/39-zu-he-zong-he.md)的区别在于每个数字只能使用一次. 为了防止第一个例子中`[1, 1, 6]`和`[6, 1, 1]`同时出现, 使用与39题中一样的方法, 需要先进行排序, 然后记录每一层开始的位置, 而与39层不同的是, 因为不能重复, 下一层的寻找要从之后一个位置开始.

另外数组中有重复的元素, 同一层搜索中, 两个同样元素在排序后紧邻, 搜索出来的结果也是一样的. 因此在每一层可以维护一个哈希表, 记录本层中搜索过的元素. 如果当前元素在之前搜索过, 就可以剪枝了.

```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        results = []
        candidates.sort()

        def dfs(path, t, start):
            if t < 0:
                return
            if t == 0:
                results.append(path[:])

            seen = set()
            for i in range(start, n):
                if candidates[i] in seen:
                    continue
                seen.add(candidates[i])
                path.append(candidates[i])
                dfs(path, t - candidates[i], i + 1)
                path.pop()

        dfs([], target, 0)
        return results
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/40-zu-he-zong-he-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.