一、题目
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Constraints:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
二、题解
使用used数组进行去重
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<int>& used){
if(sum > target) return;
if(sum == target){
res.push_back(path);
return;
}
for(int i = startIndex;i < candidates.size();i++){
if(i > 0 && candidates[i-1] == candidates[i] && used[i-1] == 0)continue;
sum += candidates[i];
used[i] = 1;
path.push_back(candidates[i]);
backtracking(candidates,target,sum,i+1,used);
sum -= candidates[i];
used[i] = 0;
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int n = candidates.size();
vector<int> used(n,0);
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0,used);
return res;
}
};
使用startIndex进行去重
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
if(sum > target) return;
if(sum == target){
res.push_back(path);
return;
}
for(int i = startIndex;i < candidates.size() && candidates[i] + sum <= target;i++){
if(i > startIndex && candidates[i-1] == candidates[i])continue;
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates,target,sum,i+1);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int n = candidates.size();
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0);
return res;
}
};
