题目

给定一个整数数组 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 中的所有元素 互不相同

注意：本题与主站 78 题相同：

解题思路分析

1、回溯；时间复杂度O(n*2^n)，空间复杂度O(n*2^n)

var res [][]int

func subsets(nums []int) [][]int {
   res = make([][]int, 0)
   dfs(nums, make([]int, 0), 0)
   return res
}

func dfs(nums []int, arr []int, level int) {
   temp := make([]int, len(arr))
   copy(temp, arr)
   res = append(res, temp)
   for i := level; i < len(nums); i++ {
      //dfs(nums, append(arr, nums[i]), i+1)
      arr = append(arr, nums[i])
      dfs(nums, arr, i+1)
      arr = arr[:len(arr)-1]
   }
}

2、迭代；时间复杂度O(n*2^n)，空间复杂度O(n*2^n)

func subsets(nums []int) [][]int {
   res := make([][]int, 0)
   res = append(res, []int{})
   for i := 0; i < len(nums); i++ {
      temp := make([][]int, len(res))
      for key, value := range res {
         value = append(value, nums[i])
         temp[key] = append(temp[key], value...)
      }
      for _, v := range temp {
         res = append(res, v)
      }
   }
   return res
}

3、位运算；时间复杂度O(n*2^n)，空间复杂度O(n*2^n)

func subsets(nums []int) [][]int {
   res := make([][]int, 0)
   n := len(nums)
   left := 1 << n
   right := 1 << (n + 1)
   for i := left; i < right; i++ {
      temp := make([]int, 0)
      for j := 0; j < n; j++ {
         if i&(1<

4、回溯；时间复杂度O(n*2^n)，空间复杂度O(n*2^n)

var res [][]int

func subsets(nums []int) [][]int {
   res = make([][]int, 0)
   dfs(nums, make([]int, 0), 0)
   return res
}

func dfs(nums []int, arr []int, level int) {
   if level >= len(nums) {
      temp := make([]int, len(arr))
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   dfs(nums, arr, level+1)
   dfs(nums, append(arr, nums[level]), level+1)
}

总结

Medium题目，题目同leetcode 78.子集；类似的题目还有：
面试题08.04.幂集；
leetcode 1239.串联字符串的最大长度；
leetcode 1863.找出所有子集的异或总和再求和