刷题分享12_3

刷题分享

这两道题目均是子集问题，其实核心与组合问题一样，不同之处在于组合问题只有在叶子节点才收集结果（即存在终止条件），而子集问题则是要在每一个节点处都收集结果。第二个题还多加了一个去重的逻辑，大体是：使用一个used数组，先对原数组排序，如果遍历到了两个相邻的元素相同，那么要看此时前一个元素在这层递归之前有没有调用过，如果调用过，说明这两个相同数字会在一个结果集里，则无需操作。如果前一个数字没有调用过，说明这两个数字不出现在同一个结果集里，就会造成重复，所以此时应该剪枝

1.（力扣78）

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;

    void backtracking(vector<int>& nums,int startindex){
        res.push_back(path);
        if(startindex>=nums.size()){
            return ;
        }
        for(int i=startindex;i<nums.size();i++){
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return res;
    }
};

2.（力扣90）

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    
    void backtracking(vector<int>& nums,vector<int>& used,int startindex){
        res.push_back(path);
        if(startindex>=nums.size()){
            return ;
        }
        for(int i=startindex;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
                continue;
            }
            path.push_back(nums[i]);
            used[i]=1;
            backtracking(nums,used,i+1);
            path.pop_back();
            used[i]=0;
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int>used(nums.size(),0);
        backtracking(nums,used,0);
        return res;
    }
};