[LeetCode] 78. Subsets #78

grandyang · 2019-05-30T16:14:43Z

请点击下方图片观看讲解视频
 Click below image to watch YouTube Video

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

这道求子集合的问题，由于其要列出所有结果，按照以往的经验，肯定要是要用递归来做。这道题其实它的非递归解法相对来说更简单一点，下面先来看非递归的解法，最开始博主在做的时候，是想按照子集的长度由少到多全部写出来，比如子集长度为0的就是空集，空集是任何集合的子集，满足条件，直接加入。下面长度为1的子集，直接一个循环加入所有数字，子集长度为2的话可以用两个循环，但是这种想法到后面就行不通了，因为循环的个数不能无限的增长，所以必须换一种思路。这里可以一位一位的往上叠加，比如对于题目中给的例子 [1,2,3] 来说，最开始是空集，那么现在要处理1，就在空集上加1，为 [1]，现在有两个子集 [] 和 [1]，下面来处理2，在之前的子集基础上，每个都加个2，可以分别得到 [2]，[1, 2]，那么现在所有的子集合为 [], [1], [2], [1, 2]，同理，处理3的情况可得 [3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了，代码如下：

解法一：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res(1);
        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;
    }
};

整个添加的顺序为：

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

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

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

解法二：

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

整个添加的顺序为：

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

最后再来看一种解法，这种解法是 CareerCup 书上给的一种解法，想法也比较巧妙，把数组中所有的数分配一个状态，true 表示这个数在子集中出现，false 表示在子集中不出现，那么对于一个长度为n的数组，每个数字都有出现与不出现两种情况，所以共有 2n 中情况，那么把每种情况都转换出来就是子集了，还是用题目中的例子, [1 2 3] 这个数组共有8个子集，每个子集的序号的二进制表示，把是1的位对应原数组中的数字取出来就是一个子集，八种情况都取出来就是所有的子集了，参见代码如下：

| 1 | 2 | 3 | Subset
---|---|---|---|---
0 | F | F | F | []
1 | F | F | T | 3
2 | F | T | F | 2
3 | F | T | T | 23
4 | T | F | F | 1
5 | T | F | T | 13
6 | T | T | F | 12
7 | T | T | T | 123

解法三：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int max = 1 << nums.size();
        for (int k = 0; k < max; ++k) {
            vector<int> cur = convertIntToSet(nums, k);
            res.push_back(cur);
        }
        return res;
    }
    vector<int> convertIntToSet(vector<int>& nums, int k) {
        vector<int> sub;
        int idx = 0;
        for (int i = k; i > 0; i >>= 1) {
            if ((i & 1) == 1) {
                sub.push_back(nums[idx]);
            }
            ++idx;
        }
        return sub;
    }
};

Github 同步地址：

#78

类似题目：

Subsets II

Generalized Abbreviation

Letter Case Permutation

Find Array Given Subset Sums

Count Number of Maximum Bitwise-OR Subsets

参考资料：

https://leetcode.com/problems/subsets/

https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation

https://leetcode.com/problems/subsets/discuss/27278/C%2B%2B-RecursiveIterativeBit-Manipulation