40. Combination Sum II
Given a collection of candidate numbers (candidates
) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sums to target
.
Each number in candidates
may only be used once in the combination.
Note:
- All numbers (including
target
) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
思路
和 39. Combination Sum 思路一致,不同的两点:
Each number in
candidates
may only be used once in the combination.The solution set must not contain duplicate combinations.
第一点,每个数字只能使用一次,在递归时,下一个传参index加一即可;
第二点,必须包含不同的组合,首先想到的是用 std::set<vector<int>>
来存储返回值,但效率太低。另一种处理方式是在递归时增加判断条件,判断当前索引下的candidates值和前一个索引是否相同,相同则直接跳过该次递归:if (i > index && candidates.at(i) == candidates.at(i-1))
C++11
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
std::sort(candidates.begin(), candidates.end());
dfs(candidates, target, vector<int>{}, 0, res);
return res;
}
void dfs(const vector<int> &candidates, int target, vector<int> curr, size_t index, vector<vector<int>> &res) {
if (target == 0) {
res.emplace_back(curr);
return;
}
for (auto i = index; i < candidates.size(); ++i) {
if (i > index && candidates.at(i) == candidates.at(i-1))
continue;
else if (candidates[i] <= target) {
curr.emplace_back(candidates[i]);
dfs(candidates, target - candidates[i], curr, i + 1, res);
curr.pop_back();
} else break;
}
}
};