LeetCode 78. Subsets

原题目：

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:

[
  [],
  [],
  [],
  [,,],
  [,],
  [,],
  [,],
  []
]
           

题目翻译：

给出一个不含重复元素的整型数组，找到所有该数组的子集，返回的结果不能包含重复的子集。

思路：

这是一道经典的子集树问题，可以直接用回溯法（Backtracking）解决（也可称之为递归法，Recursive）。查看答案之后发现，还有另外两种方案可以选择，三种方案分别是：回溯（Backtracking），迭代（Iterative），位操作（Bit Manipulation）。在此做一个整理。

方案一：回溯（Backtracking）

根据深度优先搜索（DFS）的思想实现。

AC代码如下，（C++，6ms）

class Solution {
public:
    void backtracking(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]);
            backtracking(nums, i + , sub, subs);
            sub.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs;
        vector<int> sub;  
        backtracking(nums, , sub, subs);
        return subs; 
    }
};
           

方案二：迭代（Iterative）

因为n个元素的集合一共有 2n 个子集（包括空集和集合本身），所以据此可以得到一个子集的生成策略，以[1, 2, 3]为例：

0）初始结果为只包含空集的集合：

subs = [ [] ];
           

1）将结果里的所有集合复制一次：

subs = [ [], [] ];
           

把第一个元素放入所有新生成的集合的尾部：

subs = [ [], [1] ];
           

2）重复步骤1，放入第二个元素，边复制边放入：

subs = [ [], [1], [] ];
 subs = [ [], [1], [2] ];
 subs = [ [], [1], [2], [1] ];
 subs = [ [], [1], [2], [1, 2] ];
           

3）重复步骤1，放入第三个元素：

subs = [ [], [1], [2], [1, 2], [] ];
 subs = [ [], [1], [2], [1, 2], [3] ];
 subs = [ [], [1], [2], [1, 2], [3], [1] ];
 subs = [ [], [1], [2], [1, 2], [3], [1, 3] ];
 subs = [ [], [1], [2], [1, 2], [3], [1, 3], [2] ];
 subs = [ [], [1], [2], [1, 2], [3], [1, 3], [2, 3] ];
 subs = [ [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2] ];
 subs = [ [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3] ];
           

AC代码如下，（C++，6ms）

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs(, vector<int>());
        for (int i = ; i < nums.size(); i++) {
            int n = subs.size();
            for (int j = ; j < n; j++) {
                subs.push_back(subs[j]); 
                subs.back().push_back(nums[i]);
            }
        }
        return subs;
    }
}; 
           

方案三：位操作（Bit Manipulation）

这个方案也是利用了n个元素的集合一共有 2n 个子集的性质，对集合中的每一个元素，将其插入所在的子集里面。还是以[1, 2, 3]为例：

0）初始结果为包含8个空集的集合（ 23=8 ）：

subs = [ [], [], [], [], [], [], [], [] ];
           

1）将第一个元素插入，隔 20=1 个插入连续的1个：

subs = [ [], [1], [], [1], [], [1], [], [1] ];
           

2）将第二个元素插入，隔 21=2 个插入连续的2个：

subs = [ [], [1], [2], [1, 2], [], [1], [2], [1, 2] ];
           

3）将第三个元素插入，隔 22=4 个插入连续的4个：

subs = [ [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3] ];
           

4）由于其中多处的值是2的幂次方，因此可以使用位运算的移位操作和与操作提高效率。

AC代码如下，（C++，3ms）

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int num_subset =  << nums.size();
        vector<vector<int> > subs(num_subset, vector<int>());
        for (int i = ; i < nums.size(); i++)
            for (int j = ; j < num_subset; j++)
                if ((j >> i) & )
                    subs[j].push_back(nums[i]);
        return subs;  
    }
};