491.递增子序列

这个回溯的剪枝操作真的死也想不到。太奇葩了。我以为既要树层去重又要树枝去重，结果就是一个树层去重。

class Solution {

    private:

    vector> res;

    vector path;

    void back(vector nums,int index){

        if(path.size()>=2)

        res.push_back(path);

        if(index==nums.size()){

            return ;

        }

        unordered_set used;

        for(int i=index;i

            if((!path.empty()&&nums[i]

            continue;

            used.insert(nums[i]);

            path.push_back(nums[i]);

            back(nums,i+1);

            path.pop_back();

        }

    }

public:

    vector> findSubsequences(vector& nums) {

        back(nums,0);

        return res;

    }

};

46.全排列

只能说代码看起来简单，但难想，回溯杀我啊。剪不断，理还乱。这里的终止条件不太一样，path数目够才终止。

class Solution {

    private:

    vector> res;

    vector path;    

    void back(vector nums,vector used){

        if(path.size()==nums.size()){

        res.push_back(path);

        return;}

        for(int i=0;i

            if(used[i]==true)

            continue;

            path.push_back(nums[i]);

            used[i]=true;

            back(nums,used);

            path.pop_back();

            used[i]=false;

        }

    }

public:

    vector> permute(vector& nums) {

        vector used(nums.size(),false);

        back(nums,used);

        return res;

    }

};