LeetCode 78, 90. Subsets i, ii

1.タイトルの説明
Given a set of distinct integers, nums, return all possible subsets.
Note: Elements in a subset must be in non-descending order. 78. The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
90.Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
2.問題の解き方
この2つのテーマは非常に似ていて、私たちが考えている解法は再帰的に処理することであり、GrayCodeの思想に似ていて、重複要素がある場合、重複しないことを保証することに注意しなければならない.
3. code
3.1 90 Recursive
現在のエレメントが前のエレメントと同じ場合のtrickに注意

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> tmp, res{ vector<int>() };
        for (int i = 0; i != nums.size(); i++){
            tmp = res;
            for (int j = 0; j != res.size(); j++){
                vector<int> item = res[j];
                item.push_back(nums[i]);

                if (find(tmp.begin(), tmp.end(), item) == tmp.end())
                    tmp.push_back(item);
            }

            res = tmp;
        }
        return res;
    }
};

3.2 90 search

class Solution {
public:
    // @para : depth,     
    // k,      
    // index,     nums    
    void _subset(vector<int> & nums, int depth, int k, int index){
        if (depth == k && index <= nums.size()){
            m_res.push_back(m_cur);
            return;
        }

        if (index > nums.size())
            return;

        m_cur.push_back(nums[index]);
        _subset(nums, depth + 1, k, index + 1);
        m_cur.pop_back();

        //             
        int myindex = index;
        if (index == nums.size()){
            return;
        }
        else{
            for (int i = index; i != nums.size(); i++){
                if (nums[index] == nums[i]){
                    myindex++;
                    continue;
                }
                else{
                    break;
                }
            }
        }

        _subset(nums, depth, k, myindex);
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        if (nums.size() == 0)
            return m_res;

        sort(nums.begin(), nums.end());
        for (int i = 0; i != nums.size() + 1; i++){
            _subset(nums, 0, i, 0);
        }
        return m_res;
    }

private:
    vector<vector<int>> m_res;
    vector<int> m_cur;
};

3.3 78 iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> tmp, res{ vector<int>() };
        for (int i = 0; i != nums.size(); i++){
            tmp = res;
            for (int j = 0; j != res.size(); j++){
                vector<int> item = res[j];
                item.push_back(nums[i]);

                //if (find(tmp.begin(), tmp.end(), item) == tmp.end())
                tmp.push_back(item);
            }

            res = tmp;
        }
        return res;
    }
};

3.4 78 backtracing

class Solution {
public:
    void _subsets(vector<int> & nums, int k, int depth, int index){
        if (depth == k){
            m_res.push_back(m_cur);
            return;
        }

        if (index >= nums.size())
            return;

        m_cur.push_back(nums[index]);
        _subsets(nums, k, depth + 1, index + 1);
        m_cur.pop_back();
        _subsets(nums, k, depth, index + 1);

    }

    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.size() == 0)
            return vector<vector<int>>{vector<int>()};

        sort(nums.begin(), nums.end());
        for (int i = 0; i != nums.size() + 1; i++)
            _subsets(nums, i, 0, 0);

        return m_res;
    }

private:
    vector<vector<int>> m_res;
    vector<int> m_cur;
};

4.大神解法
4.1 90重複要素を特殊なノードとして扱う

/* To solve this problem, it is helpful to first think how many subsets are there. If there is no duplicate element, the answer is simply 2^n, where n is the number of elements. This is because you have two choices for each element, either putting it into the subset or not. So all subsets for this no-duplicate set can be easily constructed: num of subset (1 to 2^0) empty set is the first subset (2^0+1 to 2^1) add the first element into subset from (1) (2^1+1 to 2^2) add the second element into subset (1 to 2^1) (2^2+1 to 2^3) add the third element into subset (1 to 2^2) .... (2^(n-1)+1 to 2^n) add the nth element into subset(1 to 2^(n-1)) Then how many subsets are there if there are duplicate elements? We can treat duplicate element as a spacial element. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset. Therefore, we are given an array (a1, a2, a3, ..., an) with each of them appearing (k1, k2, k3, ..., kn) times, the number of subset is (k1+1)(k2+1)...(kn+1). We can easily see how to write down all the subsets similar to the approach above. */
    class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > totalset = {{}};
        sort(S.begin(),S.end());
        for(int i=0; i<S.size();){
            int count = 0; // num of elements are the same
            while(count + i<S.size() && S[count+i]==S[i])  count++;
            int previousN = totalset.size();
            for(int k=0; k<previousN; k++){
                vector<int> instance = totalset[k];
                for(int j=0; j<count; j++){
                    instance.push_back(S[i]);
                    totalset.push_back(instance);
                }
            }
            i += count;
        }
        return totalset;
        }
};

4.2 90 iterative

/* If we want to insert an element which is a dup, we can only insert it after the newly inserted elements from last step. */

vector<vector<int> > subsetsWithDup(vector<int> &S) {
    sort(S.begin(), S.end());
    vector<vector<int>> ret = {{}};
    int size = 0, startIndex = 0;
    for (int i = 0; i < S.size(); i++) {
        startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;
        size = ret.size();
        for (int j = startIndex; j < size; j++) {
            vector<int> temp = ret[j];
            temp.push_back(S[i]);
            ret.push_back(temp);
        }
    }
    return ret;
}

4.3 backtracing

/* The characteristics of C++ reference is an outstanding tool for backtracking algorithm! let us use [1,2,3,4] as an example to explain my solution: subsets([1,2,3,4]) = [] // push(1) [1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack. // pop(), push(2) [2, subsets([3,4])] // pop(), push(3) [3, subsets([4])] // pop(), push(4) [4, subsets([])] // pop() Accepted 10ms c++ solution use backtracking for Subsets */

class Solution {
public:
    std::vector<std::vector<int> > subsets(std::vector<int> &nums) {
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int> > res;
        std::vector<int> vec;
        subsets(res, nums, vec, 0);
        return res;
    }
private:
    void subsets(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
        res.push_back(vec);
        for (int i = begin; i != nums.size(); ++i) {
            vec.push_back(nums[i]);
            subsets(res, nums, vec, i + 1);
            vec.pop_back();
        }
    }
};
/* Accepted 10ms c++ solution use backtracking for Subsets II */

class Solution {
public:
    std::vector<std::vector<int> > subsetsWithDup(std::vector<int> &nums) {
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int> > res;
        std::vector<int> vec;
        subsetsWithDup(res, nums, vec, 0);
        return res;
    }
private:
    void subsetsWithDup(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
        res.push_back(vec);
        for (int i = begin; i != nums.size(); ++i)
            if (i == begin || nums[i] != nums[i - 1]) { 
                vec.push_back(nums[i]);
                subsetsWithDup(res, nums, vec, i + 1);
                vec.pop_back();
            }
    }
};

4.4 iterative/backtracing/bit manipulation

/* Recursive (Backtracking) This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method. */
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> subs;
        vector<int> sub;  
        genSubsets(nums, 0, sub, subs);
        return subs; 
    }
    void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& subs) {
        subs.push_back(sub);
        for (int i = start; i < nums.size(); i++) {
            sub.push_back(nums[i]);
            genSubsets(nums, i + 1, sub, subs);
            sub.pop_back();
        }
    }
};
/* Iterative This problem can also be solved iteratively. Take [1, 2, 3] in the problem statement as an example. The process of generating all the subsets is like: Initially: [[]] Adding the first number to all the existed subsets: [[], [1]]; Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]]; Adding the third number to all the existed subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]. Have you got the idea :-) The code is as follows. */
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> subs(1, vector<int>());
        for (int i = 0; i < nums.size(); i++) {
            int n = subs.size();
            for (int j = 0; j < n; j++) {
                subs.push_back(subs[j]); 
                subs.back().push_back(nums[i]);
            }
        }
        return subs;
    }
}; 
/* Bit Manipulation This is the most clever solution that I have seen. The idea is that to give all the possible subsets, we just need to exhaust all the possible combinations of the numbers. And each number has only two possibilities: either in or not in a subset. And this can be represented using a bit. There is also another a way to visualize this idea. That is, if we use the above example, 1 appears once in every two consecutive subsets, 2 appears twice in every four consecutive subsets, and 3 appears four times in every eight subsets, shown in the following (initially the 8 subsets are all empty): [], [], [], [], [], [], [], [] [], [1], [], [1], [], [1], [], [1] [], [1], [2], [1, 2], [], [1], [2], [1, 2] [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3] The code is as follows. */
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int num_subset = pow(2, nums.size()); 
        vector<vector<int> > res(num_subset, vector<int>());
        for (int i = 0; i < nums.size(); i++)
            for (int j = 0; j < num_subset; j++)
                if ((j >> i) & 1)
                    res[j].push_back(nums[i]);
        return res;  
    }
};
/* Well, just a final remark. For Python programmers, this may be an easy task in practice since the itertools package has a function combinations for it :-) */

4.5 bit manipulation explaination

This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic.

 Number of subsets for {1 , 2 , 3 } = 2^3 .
 why ? 
case    possible outcomes for the set of subsets
  1   ->          Take or dont take = 2 
  2   ->          Take or dont take = 2  
  3   ->          Take or dont take = 2 

therefore , total = 2*2*2 = 2^3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }

Lets assign bits to each outcome  -> First bit to 1 , Second bit to 2 and third bit to 3
Take = 1
Dont take = 0

0) 0 0 0  -> Dont take 3 , Dont take 2 , Dont take 1 = { } 
1) 0 0 1  -> Dont take 3 , Dont take 2 ,   take 1       =  {1 } 
2) 0 1 0  -> Dont take 3 ,    take 2       , Dont take 1 = { 2 } 
3) 0 1 1  -> Dont take 3 ,    take 2       ,      take 1    = { 1 , 2 } 
4) 1 0 0  ->    take 3      , Dont take 2  , Dont take 1 = { 3 } 
5) 1 0 1  ->    take 3      , Dont take 2  ,     take 1     = { 1 , 3 } 
6) 1 1 0  ->    take 3      ,    take 2       , Dont take 1 = { 2 , 3 } 
7) 1 1 1  ->    take 3     ,      take 2     ,      take 1     = { 1 , 2 , 3 } 

In the above logic ,Insert S[i] only if (j>>i)&1 ==true   { j E { 0,1,2,3,4,5,6,7 }   i = ith element in the input array }

element 1 is inserted only into those places where 1st bit of j is 1 
   if( j >> 0 &1 )  ==> for above above eg. this is true for sl.no.( j )= 1 , 3 , 5 , 7 

element 2 is inserted only into those places where 2nd bit of j is 1 
   if( j >> 1 &1 )  == for above above eg. this is true for sl.no.( j ) = 2 , 3 , 6 , 7

element 3 is inserted only into those places where 3rd bit of j is 1 
   if( j >> 2 & 1 )  == for above above eg. this is true for sl.no.( j ) = 4 , 5 , 6 , 7 

Time complexity : O(n*2^n) , for every input element loop traverses the whole solution set length i.e. 2^n