今天很奇怪，我用的是dfs,AC代码是
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> vec;
dfs(result,vec,candidates,target,0,0);
return result;
}
void dfs(vector<vector<int>>& result,vector<int> vec,vector<int> candidates,int target,int sum,int start){
if(sum==target){
result.push_back(vec);
return;
}
else if(sum>target)
return;
for(int i=start;i<candidates.size();i++){
vec.push_back(candidates[i]);
dfs(result,vec,candidates,target,sum+candidates[i],i);
vec.pop_back();
}
}
};
但是前面一直用下面的代码，过不了
void dfs(vector<vector<int>>& result,vector<int> vec,vector<int> candidates,int target,int sum,int start){
if(sum==target){
result.push_back(vec);
return;
}
for(int i=start;i<candidates.size();i++){
sum +=candidates[i]; //这里
if(sum>target)
return;
vec.push_back(candidates[i]);
dfs(result,vec,candidates,target,sum,i);
}
}
};
后来发现我这样写会改变sum的值，下次要注意了。
