九月首发,教师节快乐呀!
这个题,数字可以重复选,那就直接回溯呀!!!
class Solution{ vector<int> res; vector<vector<int>> ans; public: void combine(vector<int>& candidates, int target,int i){ if(target==0){ ans.push_back(res); return ; } if(target<0){ return ; } for (int j = i; j < candidates.size(); ++j) { res.push_back(candidates[j]); combine(candidates,target-candidates[j],j);//递归还是j res.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { combine(candidates,target,0); return ans; } };
再看第二题
这个题本来以为就把那个地方改为j+1就行了,结果直接WA了
想想也是,[1,7]和[7,1]是一样的呀,但是你只改变了j+1是没有用的
其实去重的话,一个很重要的问题是树的层数
candidates = [1, 1, 2], target = 3,(方便起见candidates已经排序了)
class Solution { public: vector<vector<int>> ans; vector<int> num; void combine(vector<int>& candidates, int target,int i,vector<bool> used) { if (target == 0) { ans.push_back(num); return; } if (target < 0) { return; } for (int j = i; j < candidates.size(); ++j) { if(candidates[j]>target) continue; if (j > 0 && candidates[j] == candidates[j - 1] && used[j - 1] == false) { continue; } num.push_back(candidates[j]); used[j] = true; combine(candidates,target-candidates[j],j+1,used); num.pop_back(); used[j] = false; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<bool> used(candidates.size(), false); sort(candidates.begin(),candidates.end()); combine(candidates, target, 0,used); return ans; } };