08.04. Power Set LCCI 幂集(C++ 位运算)

题目

力扣原题
Write a method to return all subsets of a set. The elements in a set are pairwise distinct.

Note: The result set should not contain duplicated subsets.

Example:

Input:

nums = [1,2,3]
1

Output:

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

思路

每个数字都有“选择”和“不选择”两种情况，那么 $n$ 个数字就有 $2^n$ 个排列组合，如果用 $n$ 位 二进制数表示，$1$ 表示“选择”，$0$ 表示”不选择,则正好能表示所有情况。
如图：
$n=3$
$0\le i\le 2^n-1:[0,7]$
$0\le j\le n-1:[0,2]$

那么接下来的问题就是：

如何确认，二进制数 $i$ 的 $j$ 号位为 $1$。

与运算

i == 2 == 010(二进制) 时，和 1==001 进行与运算 $2\&1$:

      010
        &
      001
      000
1
2
3
4

得$2\&1=000=0$，现在我们知道了，0号位，即num[0] = 1 现在不可以加入到子集中。
0号位的问题解决了，那1和2号位，怎么检测？

有两种办法：

1. 让 i 继续与2 == 010 和 4 == 100做与运算，那怎么在循环中得到这么一个与运算序列呢？可以用算数左移<<，等于乘2，低位补零。

int k = 1;  // k = 0001 = 1
k = k << 1; // k = 0010 = 2
k = k << 1; // k = 0100 = 4
k = k << 1; // k = 1000 = 8
. . . 
1
2
3
4
5

2. 1 == 001 不变， 让 $i$ 算数右移>> $j$ 位，等于除2，每次检查当前的最后一位。

int i = 6, j; // i = 110 = 6

j = 0;
i >> j == 6 == 110 // 最后一位为 0, 此时 j = 0, num[0]不放入
(i >> j) & 1 ==  0 // 110 & 001 = 000 与最后一位的值相等

j = 1;
i >> j == 3 == 011 // 最后一位为 1, 此时 j = 1, num[1]放入
(i >> j) & 1 ==  1 //  011 & 001 = 001 与最后一位的值相等

j = 1;
i >> j == 1 == 001 // 最后一位为 1, 此时 j = 2, num[2]放入
(i >> j) & 1 ==  1 //  001 & 001 = 001 与最后一位的值相等

得到当前集合为 {2, 3}

而 if((i >> j) & 1 == 1) 或 if((i >> j) & 1)
就是是否加入当前集合的判断条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这两种方法的原理一样，区别只是，拿 i 还是 001 当作比对条。

代码

class Solution { // 方法一 001 当作 比对条
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        unsigned long long len = 1 << nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < len; i++) {
            vector<int> sub_set = {};
            for (int j = 0, one = 1; j < nums.size(); j++) {
            	// 这个 one 就是我们的比对条
            	// 一开始 ‘1’在最右边, 或者说，最低位
            	// 比对完，就 << 左移一位
            	// 下一个循环就能比对下一位
                if (i & one)
                	// 二进制数 i 的 j 号位为 1
                	// 加入到子集中
                    sub_set.push_back(nums[j]);
                one = one << 1;
            }
            ans.push_back(sub_set);
        }
        return ans;
    }
};

class Solution { // 方法二 i 当作 比对条
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        unsigned long long len = 1 << nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < len; i++) {
            vector<int> sub_set = {};
            for (int j = 0; j < nums.size(); j++) {
                if ((i >> j) & 1)
                    sub_set.push_back(nums[j]);
            }
            ans.push_back(sub_set);
        }
        return ans;
    }
};
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
30
31
32
33
34
35
36
37
38
39
40

我更喜欢方法一，更好理解，从低到高，一位一位地比对。

代码(回溯法)

class Solution {
public:
    void dfs(vector<vector<int>> &ans, vector<int> &cur, vector<int> &nums, int start) {
        ans.push_back(cur);
        for (int i = start; i < nums.size(); i++) {
            cur.push_back(nums[i]);
            dfs(ans, cur, nums, i + 1); // 是 ｉ + 1 ！！！
            cur.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> cur = {};
        dfs(ans, cur, nums, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17