Description
Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
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
|
求所有子集（幂集），包含一个空集。
## Solution
### 回溯（Backtracking）
与上一题[《LeetCode 77. Combinations》](/leetcode/077-combinations/)
的思路相似
可以递归回溯，分别找出`k`从`0->len(nums)`的所有组合。
### 位运算（Bit Manipulation）
设长度`l = len(nums)`，设有一个`l`位二进制数`flag`，每一位对应`nums`中的一个数字。
如果这一位为`1`，表示对应数字显示；为`0`表示隐藏。
那么`flag`的所有二进制组合可以对应`nums`的所有子集
很容易得到：$ flag \in [0, 2^l) $
|
比如题目中的例子：
nums = [1, 2, 3]
when flag=0 b(000) => []
when flag=1 b(001) => [ , , 3]
when flag=2 b(010) => [ , 2, ]
when flag=3 b(011) => [ , 2, 3]
when flag=4 b(100) => [1, , ]
when flag=5 b(101) => [1, , 3]
when flag=6 b(110) => [1, 2, ]
when flag=7 b(111) => [1, 2, 3]
1
2
3
4
5
6
7
|
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
| func subsets(nums []int) [][]int {
l := len(nums)
// power: 2^l
n := 1 << uint(l)
result := [][]int{}
for i := 0; i < n; i++ {
// each bit means a number in []nums
// if the bit is 1, the number is visible
// else the number is invisible
flag := i
r := []int{}
for j := 0; j < l; j++ {
// check if this number visible
if flag&0x01 > 0 {
r = append(r, nums[j])
}
// right-shift
flag >>= 1
}
result = append(result, r)
}
return result
}
|
|