39. Type：medium
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidateswhere the candidate numbers sums to target.
The same repeated number may be chosen from candidatesunlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input:candidates =[2,3,6,7], target =7,A solution set is:[ [7], [2,2,3]]
Example 2:
Input:candidates = [2,3,5], target = 8,A solution set is:[ [2,2,2,2], [2,3,3], [3,5]]
在一个非重复数组中找到几个元素，使得其和等于target，元素可以多次使用。
递归法，对于任何一个vector和target。首先排序，然后将i从0遍历到n-1，取vector[i]的值，并在vector[i]及其值后的数组中找和为target-vector[i]的数组，最后返回vector[i]+该数组。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
sort(candidates.begin(), candidates.end());
int len = candidates.size();
for(int i=0; i<len; i++){
if(candidates[i] == target){
ret.push_back({candidates[i]});
break;
}
if(candidates[i] > target) break;
vector<int> vec = vector<int>(candidates.begin()+i, candidates.end());
vector<vector<int>> temp = combinationSum(vec, target - candidates[i]);
for(int j=0; j<temp.size(); j++){
temp[j].push_back(candidates[i]);
sort(temp[j].begin(), temp[j].end());
ret.push_back(temp[j]);
}
}
return ret;
}
};
40、Type：medium
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidateswhere the candidate numbers sums to target.
Each number in candidatesmay 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题不同的是，数组中可能有重复元素，且每个元素只能用一次。但想法与上题相同。
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ret;
int n = candidates.size();
for(int i=0; i<n; i++){
if(candidates[i] == target){
ret.push_back({candidates[i]});
break;
}
if(candidates[i] > target) break;
vector<int> vec = vector<int>(candidates.begin()+i+1, candidates.end());
vector<vector<int>> temp = combinationSum2(vec, target - candidates[i]);
for(int j=0; j<temp.size(); j++){
temp[j].push_back(candidates[i]);
sort(temp[j].begin(), temp[j].end());
ret.push_back(temp[j]);
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
};
