啊啊啊啊。好怀念这样的用递归保存路径然后打印出来的题目啊。好久没遇到了。
分了两种，一种是能够反复使用数组中数字的，一种是每一个数字仅仅能用一次的。事实上没有多大差别，第一种每次进入递归的时候都要从头開始尝试。另外一种要找一个标记的数组，把已经用到过的排除掉，就像生成全排列时的做法一样。
跟我一样用引用保存中间结果的话。要注意回退的情况。
另外一种回退时，要把用到的那个数也恢复为可用，就全然像全排列时做的一样。破例贴两个题的代码。由于他们是在是不值得用两片文章来写。
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;
}
};