## [Leetcode]40. Combination Sum II(C++)

### 题目描述

Given an array of distinct integers `candidates` and a target integer `target`, return a list of all unique combinations of `candidates` where the chosen numbers sum to `target`. You may return the combinations in any order.

Each number in `candidates` may only be used once in the combination.

### 例子

#### 例子 1

Input: `candidates = [10,1,2,7,6,1,5], target = 8` Output: `[` `[1,1,6],` `[1,2,5],` `[1,7],` `[2,6]` `]`

#### 例子 2

Input: `candidates = [2,5,2,1,2], target = 5` Output: `[` `[1,2,2],` `[5]` `]`

#### 例子 3

Input: Output: Explanation:

### Note

The solution set must not contain duplicate combinations.

### Constraints

• `1 <= candidates.length <= 100`
• `1 <= candidates[i] <= 50`
• `1 <= target <= 30`

### 解题思路

• 每个数字只能选一次
• 返回的组合中不能包含的重复的子集：
• 例如，输入是 `[2,2,2]`，要求目标是 `4` 的话，结果中只能出现一次 `[2,2]`

• DFS 内部循环递归调用时，传入的索引改成 `i + 1`，避免同一位置多次使用
• 对输入数组进行排序，在循环时如果前一位数字和当前数字一致时，跳过当前数字（因为这种情况已经考虑过了）

``````#include <vector>
#include <algorithm>

class Solution {
public:
std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
std::vector<int> candidate;
std::vector<std::vector<int>> result;
std::sort(candidates.begin(), candidates.end());
dfs(candidates, 0, target, candidate, result);
return result;
}

private:
void dfs(const std::vector<int>& candidates, int idx, int res, std::vector<int>& candidate, std::vector<std::vector<int>>& result) {
if (res == 0) {
result.push_back(candidate);
} else if (res < 0) {
return;
}

for (int i = idx; i < candidates.size(); ++i) {
if (i != idx && candidates[i] == candidates[i - 1]) continue;
candidate.push_back(candidates[i]);
dfs(candidates, i + 1, res - candidates[i], candidate, result);
candidate.pop_back();
}
}
};
``````
• 时间复杂度: O(n!)
• 空间复杂度: O(Cnk)

GitHub 代码同步地址： 40.CombinationSumIi.cpp