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],
  []
]

求所有子集(幂集),包含一个空集。

Solution

回溯(Backtracking)

与上一题《LeetCode 77. Combinations》 的思路相似

可以递归回溯,分别找出k0->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
 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
}

Similar Problem