Leetcode - Subsets I，II

Leetcode - 078. Subsets

这道题重定义了什么叫可行解：
一般而言，可行解需要满足强约束性条件集，而本题的可行解就是单一弱约束性条件(distinct integers,只需要当前集合内的元素不重复即可算作一个可行解) ，算是比较简单的入门级dfs + backtracing 题目。

class Solution {
public:

    void dfs(vector<vector<int>> & vct,vector<int> &cur,vector<int>& nums,int index)
    {
        vct.push_back(cur);
        int n = nums.size();
        if(index >= n)
            return;
        for(int i = index;i < n;++i)
        {
            cur.push_back(nums[i]);
            dfs(vct,cur,nums,i + 1);
            cur.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> vct;
        vector<int> cur;
        dfs(vct,cur,nums,0);
        return vct;
    }
};

Leetcode - 090. Subsets II

diff vs the pre version:
有重复的元素怎么算？相关的思路雷同于Leetcode - 040. Combination Sum II

class Solution {
public:

    void dfs(vector<vector<int>> &vct, vector<int> &cur, vector<int>& nums,vector<int> & used,int index)
    {
        vct.push_back(cur);
        int n = nums.size();
        if (index >= n)
            return;
        for (int i = index; i < n; ++i)
        {
            if (used[i] == 0)
            {
                int j = i - 1;
                bool repeated = false;
                while (j >= 0 && nums[j] == nums[i])
                {
                    if (used[j] == 0)
                    {
                        repeated = true;
                        break;
                    }
                    --j;
                }
                if (repeated)
                    continue;
                cur.push_back(nums[i]);
                used[i] = 1;
                dfs(vct, cur, nums, used, i + 1);
                used[i] = 0;
                cur.pop_back();
            }
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> vct;
        vector<int> cur;
        int n = nums.size();
        if (n <= 0)
            return vct;
        vector<int> used(n, 0);
        sort(nums.begin(), nums.end());
        dfs(vct, cur, nums,used,0);
        return vct;
    }
};