78. Subsets (Medium)

Given a set of distinct integers, nums, return all possible subsets.

Note: 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],
  []
]

Solution 1: Recursion 6ms

下面来看递归的解法，相当于一种深度优先搜索，参见网友JustDoIt的博客，由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

                        []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

class Solution {
    void dfs(vector<int>& nums, int j, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path); 
        for (int i = j; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            dfs(nums, i+1, path, res);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(nums, 0, path, res);
        return res;
    }
};

class Solution {
    void dfs(vector<int>& nums, int j, vector<int> path, vector<vector<int>>& res) {
        if (j == nums.size()) { res.push_back(path); return; }
        dfs(nums, j+1, path, res);
        path.push_back(nums[j]);
        dfs(nums, j+1, path, res);
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        dfs(nums, 0, {}, res);
        return res;
    }
};

Solution 2: Iteration 6ms

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: \[\[\]\]

1. Adding the first number to all the existed subsets: [[], [1]];
2. Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]];
3. 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) {
        vector<vector<int>> res(1); // empty set
        for (int i = 0; i < nums.size(); ++i) {
            int size = res.size();
            for (int j = 0; j < size; ++j) {
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
};

Solution 3: Bit Manipulation 9ms

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):

000
001
010
011
100
101
110
111
  ^
  | // move 1 pos each time

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int num_subset = pow(2, nums.size());
        vector<vector<int>> res(num_subset);
        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;
    }
};