78. 子集

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[ ],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[ ],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解法一：回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func subsets(nums []int) [][]int {
    n := len(nums)
    ans := make([][]int, int(math.Pow(2, float64(n))))
    var tmp []int
    tIdx := 0
    var backtracking func(idx int)
    backtracking = func(idx int) {
        if idx >= n {
            ans[tIdx] = append([]int(nil), tmp...)
            tIdx++
            return
        } else {
            // idx < n
            tmp = append(tmp, nums[idx])
            backtracking(idx + 1)
            tmp = tmp[:len(tmp)-1]
            backtracking(idx + 1)
        }
    }
    backtracking(0)
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func subsets(nums []int) (ans [][]int) {
    set := []int{}
    var dfs func(int)
    dfs = func(cur int) {
        if cur == len(nums) {
            ans = append(ans, append([]int(nil), set...))
            return
        }
        set = append(set, nums[cur])
        dfs(cur + 1)
        set = set[:len(set)-1]
        dfs(cur + 1)
    }
    dfs(0)
    return
}

解法二：迭代

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func subsets(nums []int) (ans [][]int) {
    n := len(nums)
    for mask := 0; mask < 1<<n; mask++ {
        set := []int{}
        for i, v := range nums {
            if mask>>i&1 > 0 {
                set = append(set, v)
            }
        }
        ans = append(ans, append([]int(nil), set...))
    }
    return
}