注意,sort的时候,千万不要直接改变list,要用临时数组来代替;因为递归过程中后面还要pop_back;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
set<vector<int>> myres;
if(candidates.empty()) return result;
vector<int> list;
dfs(candidates, myres, list, target);
for(auto iter = myres.begin(); iter != myres.end(); iter++){
result.push_back(*iter);
}
return result;
}
private:
void dfs(vector<int>& candidates, set<vector<int>>& myres, vector<int>& list, int now){
if(now < 0) return;
if(now == 0){
vector<int> tmp(list);
sort(tmp.begin(), tmp.end());//不能改变list, 要用另外的临时数组
myres.insert(tmp);
return;
}
for(int i = 0; i < candidates.size(); i++){
if(now < candidates[i] ) continue;
list.push_back(candidates[i]);
dfs(candidates, myres, list, now - candidates[i]);
list.pop_back();
}
}
};
解法二:
用一个标记,这样可以防止重复的答案,比如[2,2,3] 和[2,3,2]
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> list;
if(candidates.empty()) return result;
sort(candidates.begin(), candidates.end());
dfs(candidates, result, list, target, 0);
return result;
}
private:
void dfs(vector<int> candidates, vector<vector<int>>& result, vector<int>& list, int cur, int begin){
if(cur == 0){
result.push_back(list);
return;
}
for(int i = begin ; i < candidates.size() && candidates[i] <= cur; i++){
list.push_back(candidates[i]);
dfs(candidates, result, list, cur - candidates[i],i);//因为这个值可以重复用,一定要注意,既然在了循环里,所以要用的是i,这样可以防止重复的答案。
list.pop_back();
}
}
};
网友评论