Subsets

Problem:

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > solution;
        int size = S.size();
     
        if (size == 0)
            return solution;

        sort(S.begin(), S.end());
        vector<int> subset;
        solution.push_back(subset);
     
        for (int i = 0; i < size; i++) {
            int subset_count = solution.size();
            for (int sln_idx = 0; sln_idx < subset_count; sln_idx++) {
                subset = solution[sln_idx];
                subset.push_back(S[i]);
                solution.push_back(subset);
            }
        }
        return solution;
    }
};

=============== Alternate (Small one)=======================

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
    sort(S.begin(), S.end());
    vector<vector<int> > v(1);
    for(int i = 0; i < S.size(); ++i) {
        int j = v.size();
        while(j-- > 0) {
            v.push_back(v[j]);
            v.back().push_back(S[i]);
        }
    }
    return v;
    }
};

=================== Alternate (Bitwise) ========================

class Solution {

public:

    vector<vector<int> > subsets(vector<int> &S) {

sort(S.begin(), S.end());

int n = S.size();

vector<vector<int> > result;

for (int i = 0; i < (1 << n); i++) {

vector<int> s;

for (int j = 0; j < n; j++) {

if ((i >> j) & 1) {

s.push_back(S[j]);

}

}

result.push_back(s);

}

return result;

    }

};

============ Another attempt =========

vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > ans;
        ans.push_back(vector<int>());
        
        if (nums.size() == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }

=============================== Another =========

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        ans.push_back(vector<int>());
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(num);
                ans.push_back(tmp);
            }
        }
        
        return ans;
    }
};