78. Subsets 子集

题目

给定一个整数数组，返回所有可能的子集。子集必须是不重复的。

解析

这个问题和上一个问题相似，就是求 cn0 + cnn。
首先看看 cnk 的解法。
f(nums, k) [][]int

伪代码

len=len(nums)
if k == 0 
  return [][]int{{}}
for len >= k
  rst += nums[len-1] + f(nums[:len-1], k-1)
  len--
return rst

代码

func subsets(nums []int) [][]int {
    var rst [][]int
    for i:=0;i<=len(nums);i++ {
        tmp := sub(nums, i)
        rst=append(rst, tmp...)
    }
    return rst
}

func sub(nums []int, k int) [][]int {
    var rst [][]int
    if k == 0 {
        return [][]int{{}}
    }
    tail := len(nums)
    for tail>=k {
        tmp := sub(nums[:tail-1], k-1)
        for i := range tmp {
            rst=append(rst, append([]int{nums[tail-1]}, tmp[i]...))
        }
        tail--
    }
    return rst
}

image.png

后记

1. 此类问题，可以概括为 cnk ，排列组合问题。