LeetCode-40. 组合总和 II C++(回溯法)
阅读原文时间:2023年07月09日阅读:1

回溯法本身是种暴力解法,虽然效率之类的比较低,但是写起来比较易懂和快。在提交之后的排名也挺低的,大概就超过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);

    }
};

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器