40. Combination Sum II
Leetcode Array Backtracking题目¶
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]
]
分析¶
40题和39题相比,主要差别在每个数字只能使用一次:在explore步骤时采用i+1
参数。对于重复的结果,笨办法是使用set。
#include <algorithm>
class Solution {
public:
void combinationSum2Helper(vector<int>& candidates, int target, set<vector<int>>& res, vector<int>& chosen, int position){
if (target == 0){
// base case
res.insert(chosen);
}else{
for(int i=position; (i<candidates.size()) && (candidates[i]<=target);i++){
//choose
chosen.push_back(candidates[i]);
//explore
combinationSum2Helper(candidates, target-candidates[i], res, chosen, i+1);
//unchoose
chosen.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
set<vector<int>> res;
vector<int> chosen;
sort(candidates.begin(), candidates.end());
combinationSum2Helper(candidates, target, res, chosen, 0);
vector<vector<int>> res_final(res.begin(), res.end());
return res_final;
}
};
有一种更巧妙的办法去除重复,需要仔细分析什么时候会出现重复。其实只有一种情况,那就是在挑选下一个元素时,有前后元素相同。所以可以直接在choose步骤,增加一句
if (i&&num[i]==num[i-1]&&i>position) continue; // check duplicate combination
#include <algorithm>
class Solution {
public:
void combinationSum2Helper(vector<int>& candidates, int target, vector<vector<int>>& res, vector<int>& chosen, int position){
if (target == 0){
// base case
res.push_back(chosen);
}else{
for(int i=position; (i<candidates.size()) && (candidates[i]<=target);i++){
if ((i>position) && (candidates[i]== candidates[i-1])){// 跳过重复
continue;
} else{
//choose
chosen.push_back(candidates[i]);
//explore
combinationSum2Helper(candidates, target-candidates[i], res, chosen, i+1);
//unchoose
chosen.pop_back();
}
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> chosen;
sort(candidates.begin(), candidates.end());
combinationSum2Helper(candidates, target, res, chosen, 0);
return res;
}
};