📑 题目：78. 子集

🚀 本题 LeetCode 传送门

题目大意

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

解题思路

• 找出一个集合中的所有子集，空集也算是子集。且数组中的数字不会出现重复。用 DFS 暴力枚举即可。
• 这一题和第 90 题，第 491 题类似，可以一起解答和复习。

代码

package leetcode
import ""sort""
// 解法一
func subsets(nums []int) [][]int {
 c, res := []int{}, [][]int{}
 for k := 0; k <= len(nums); k++ {
  generateSubsets(nums, k, 0, c, &res)
 }
 return res
}
func generateSubsets(nums []int, k, start int, c []int, res *[][]int) {
 if len(c) == k {
  b := make([]int, len(c))
  copy(b, c)
  *res = append(*res, b)
  return
 }
 // i will at most be n - (k - c.size()) + 1
 for i := start; i < len(nums)-(k-len(c))+1; i++ {
  c = append(c, nums[i])
  generateSubsets(nums, k, i+1, c, res)
  c = c[:len(c)-1]
 }
 return
}
// 解法二
func subsets1(nums []int) [][]int {
 res := make([][]int, 1)
 sort.Ints(nums)
 for i := range nums {
  for _, org := range res {
   clone := make([]int, len(org), len(org)+1)
   copy(clone, org)
   clone = append(clone, nums[i])
   res = append(res, clone)
  }
 }
 return res
}
// 解法三：位运算的方法
func subsets2(nums []int) [][]int {
 if len(nums) == 0 {
  return nil
 }
 res := [][]int{}
 sum := 1 << uint(len(nums))
 for i := 0; i < sum; i++ {
  stack := []int{}
  tmp := i // i 从 000...000 到 111...111
  for j := len(nums) - 1; j >= 0; j-- { // 遍历 i 的每一位
   if tmp & 1 == 1 {
    stack = append([]int{nums[j]}, stack...)
   }
   tmp >>= 1
  }
  res = append(res, stack)
 }
 return res
}