回溯法本身是种暴力解法,虽然效率之类的比较低,但是写起来比较易懂和快。在提交之后的排名也挺低的,大概就超过8%左右。以后复习的时候再去看看题解,看看更高性能的算法。这里先暂时贴上回溯法的代码。
最后说一句,如果只是简单的用回溯法,不做优化,即使是LeetCode还是会超时,毕竟是O(2N)的复杂度,所以这里利用题干给的target,进行简单的拆分。(注释虽然没有。。。但应该还是能懂,以后再加)
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int> > result;
vector<int> item;
set<vector<int> > rset;
sort(candidates.begin(),candidates.end());
CreatSet(0,result,item,candidates,rset,target,0);
return result;
}
void CreatSet(int i ,vector<vector<int> > &result,
vector<int> &item,vector<int> & nums,
set<vector<int> > &rset,int target,int sum){
if(sum > target ||i >= nums.size()) return;
sum += nums[i];
item.push_back(nums[i]);
if(target==sum && rset.find(item) ==rset.end()){
rset.insert(item);
result.push_back(item);
}
CreatSet(i+1,result,item,nums,rset,target,sum);
item.pop_back();
sum-=nums[i];
CreatSet(i+1,result,item,nums,rset,target,sum);
}
};
手机扫一扫
移动阅读更方便
你可能感兴趣的文章