描述 Description

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

[Subsets]

分析 Analysis

方法1

搜索长度为n的子集时使用n重for循环。O(n^n)，这个复杂度绝对的不行。

方法2

用回溯法。类似深度优先搜索。因为是子集，[1,2]和[2,1]一样，所以我们的每次递归的停止条件都是到nums[]中的最后一个元素，也即指定了树向下生长时子树结点大小小于父结点。

也可以使用子集树：

方法3

迭代法。类似广度优先搜索。如[1, 2, 3]生成子集的过程：

1. Initially: [[ ]]
2. Adding the first number to all the existed subsets: [[], [1]];
3. Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]];
4. Adding the third number to all the existed subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

方法4

利用bitmap。对于子集来说，每个元素只有2种状态：在子集中，不在子集中。这刚好符合2进制，可以考虑使用bitmap的方法。

我们对每个元素一个bit：

• 0：在当前子集中

• 1：不在当前子集中

对于n个元素，一共有2^n种取法，这和子集数也是一致的。

示例：

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 }

刚好可以取尽所有元素。

也就是说，如果我们从 0 - 2^n - 1 （这里是从0-7）循环取值i，看每个值i中对应的1有哪些，如果1在第k个bit位上，就说明题目给定的数组nums中的元素nums[k]在这个子集i中。如i = 4 即 1 0 0 时，只有第2个位置为1，所以此子集中只有一个数num[2]，即{3}。

算法复杂度O(n*2^n)，一层循环从0到2^n种子集取法，二层循环看每个取法对应的2进制中的1的个数。

如果nums.size()特别大，在判断时候，检测到一个1，就去掉j中最后的1（通过j & (j - 1)），这样j == 0时就可以提前结束内层循环。但是nums.size()不可能特别大，大于32的话，子集数目就比最大4位整数还大，测试中也没有这么大的数，如果有的话就只能使用回溯了。

或者增加判断比j大的那个最大的1的位置，这样i就可以提前结束。

代码 Code

方法2：回溯

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();
        }
    }
};

[A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)]

方法3：迭代

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;
    }
};

方法4：bit操作

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &nums) {
//        sort (nums.begin(), nums.end()); //不用排序，没有说结果要有序
        int elem_num = nums.size();
        int subset_num = 1 << elem_num; //pow (2, elem_num);
        vector<vector<int> > subset_set (subset_num, vector<int>());

        for (int j = 0; j < subset_num; j++)
            for (int i = 0; i < elem_num; i++)
                if ((j >> i) & 1)
                    subset_set[j].push_back (nums[i]);
        return subset_set;
    }
};