首页 > 代码库 > leetcode第一刷_Combination Sum Combination Sum II
leetcode第一刷_Combination Sum Combination Sum II
啊啊啊啊,好怀念这种用递归保存路径然后打印出来的题目啊,好久没遇到了。
分了两种,一种是可以重复使用数组中数字的,一种是每个数字只能用一次的。其实没有多大区别,第一种每次进入递归的时候都要从头开始尝试,第二种要找一个标记的数组,把已经用到过的排除掉,就像生成全排列时的做法一样。跟我一样用引用保存中间结果的话,要注意回退的情况。第二种回退时,要把用到的那个数也恢复为可用,就完全像全排列时做的一样。破例贴两个题的代码,因为他们是在是不值得用两片文章来写。
class Solution { public: set<vector<int> > vis; bool used[1000]; void getSum(vector<int> &num, vector<vector<int> > &res, vector<int> &tpres, int target){ if(target == 0){ vector<int> sortres = tpres; sort(sortres.begin(), sortres.end()); if(vis.find(sortres) == vis.end()){ vis.insert(sortres); res.push_back(sortres); } tpres.pop_back(); return; } for(int i=0;i<num.size();i++){ if(target<num[i]) continue; if(!used[i]){ used[i] = 1; tpres.push_back(num[i]); getSum(num, res, tpres, target-num[i]); used[i] = 0; } } tpres.pop_back(); } vector<vector<int> > combinationSum2(vector<int> &num, int target) { vector<vector<int> > res; if(num.size() <= 0) return res; vector<int> tpres; memset(used, 0, sizeof(used)); getSum(num, res, tpres, target); return res; } };
class Solution { public: set<vector<int> > vis; void getSum(vector<int> &candidates, vector<vector<int> > &res, vector<int> &tpres, int target){ //cout<<target<<"*"<<endl; if(target<0){ tpres.pop_back(); return; } if(target == 0){ vector<int> sortres = tpres; sort(sortres.begin(), sortres.end()); if(vis.find(sortres) == vis.end()){ res.push_back(sortres); //for(int i=0;i<tpres.size();i++) // cout<<tpres[i]<<" "; //cout<<endl; vis.insert(sortres); } tpres.pop_back(); return; } for(int i=0;i<candidates.size();i++){ if(target<candidates[i]) continue; tpres.push_back(candidates[i]); getSum(candidates, res, tpres, target-candidates[i]); //if(!tpres.empty()) tpres.pop_back(); } if(!tpres.empty()) tpres.pop_back(); } vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > res; vector<int> tpres; if(candidates.size()<=0) return res; getSum(candidates, res, tpres, target); return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。