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: 

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路

类似于排列组合的问题，我们都可以一律利用回溯的方法来解决。在回溯的函数里，我们递归地调用函数本身，layers代表回溯的层数；nums是输入的数组，append是当前层已有的数，result是将要返回的最终结果。当回溯层数为0时，我们可以将当前层已有的数加入到result中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public void combination(int layers, List<Integer> append, int[] nums, List<List<Integer>> result){
        if (layers == 0){
            result.add(append);
        }
        else{
            for (int i = 0; i < nums.length; i++){
                List<Integer> new_append = new ArrayList<Integer>(append);
                new_append.add(nums[i]);
                int len = nums.length - i - 1;
                int[] new_nums = new int[len];
                int k = i+1;
                for(int j = 0; j < len; j++){
                    new_nums[j] = nums[k];
                    k++;
                }
                combination(layers-1, new_append, new_nums, result);
            }
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> append = new ArrayList<Integer>();
        for (int i = 0; i <= nums.length; i++){
            combination(i, append, nums, result);
        }
        return result;
    }
}

下面是利用位运算的方法解决这道题，非常巧妙。

Using 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
2
3
4
[], [], [], [], [], [], [], []
[], [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.

1
2
3
4
5
6
7
8
9
10
11
12
13
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;  
    }
};