Leetcode 78. 子集

Leetcode 78. 子集

题目

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

位运算

其实嘛,取子集这件事情,对每一个元素就两种状态,取和不取,共有 $2^{len(nums)}$种可能。这可以直接用一个二进制 bit (boolean)位向量表示:

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
nums = [1, 2, 3]

幂集 = [
[],
[1],
[2],
[1,2],
[3],
[1,3],
[2,3],
[1,2,3]
]

# 0 表示不取
# 1 表示取
对应取的状态 = [
[0, 0, 0],
[0, 0, 1],
[0, 1, 0],
[0, 1, 1],
[1, 0, 0],
[1, 0, 1],
[1, 1, 0],
[1, 1, 1]
]

可以看到,所有对应取的状态合在一起,其实就是遍历了 len(nums) 位的二进制位向量所有可能的取值。如果用整数表示二进制位向量,即遍历 [0, 1 << len(nums) - 1] 。这样实现起来很简单了,跑一个循环就行:

1
2
3
for i := 0; i < 1 << len(nums); i++ {
// ...
}

在这个遍历里,把二进制位向量映射到原数组的索引,就能取出一个子集了:

1
2
3
4
5
6
7
8
s := []int{}
for j, ii := 0, i; j < len(nums); j, ii = j+1, ii>>1 {
// 这个 for 其实就是每次从低位端 pop 一个位出来,这个位对应一个索引嘛
// pop 出的是 1 就取这个索引处的元素进子集
if ii & 1 == 1 {
s = append(s, nums[j])
}
}

合在一起,就有了完整的 Golang 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
func subsets(nums []int) [][]int {
subs := [][]int{}
for i := 0; i < 1 << len(nums); i++ {
s := []int{}
for j, ii := 0, i; j < len(nums); j, ii = j+1, ii>>1 {
if ii & 1 == 1 {
s = append(s, nums[j])
}
}
subs = append(subs, s)
}
return subs
}

啊,我写不清这个,,,我觉得二进制、位运算这种东西相当自然,就像我们算 1 + 1 很自然就得到了 2,用二进制位向量是一种很自然的事,它就该这么用,所有反倒难以解释了😂

也许这不是一个很好的思路,但从结果上来看,这个算法还是比较快的:

屏幕快照 2020-04-14 08.50.13