77. Combinations 组合

题目

给定两个整数 n 和 k，在 [1,n] 之间返回 k 个数的组合。

比如 n = 4, k =2 返回:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

由这个例子可知，其实就是求 Cnk 的排列组合。

解析

用递归求解，从 n 个数里取 k 个数，也就是说，先取一个数，然后然后在 n-1 个数里取 k-1 个数，或者 n-2 个数里取 k-1 个数。只要 n 一只大于 k。
f(n,k) = (n + f(n-1,k-1)) + (n-1 + f(n-2, k-1)) + ... +(n-k+2,f(n-k+1, k-1))

伪代码

if k==1
  return []int{{1}...{n}}
for n>=k
 rst = n+combin(n-1, k-1)
 n--

代码

func combine(n int, k int) [][]int {
    var rst [][]int
    if k == 0 {
        return [][]int{{}}
    }
    for ;n>=k;n-- {
        tmp := combine(n-1,k-1)
        for i := range tmp {
            rst=append(rst, append([]int{n}, tmp[i]...))
        }
    }
    return rst
}

image.png

后记

1. 牢记递归公式的含义，f(n,k) 指的是在n个数中取k个值的排列。即随意取一个值后，在剩余值里取 k-1 个值。为了避免重复，只能向后取，不能向前取。
2. k==0 和 k == 1 均可作为递归终止条件，取 0 ，逻辑简单，代码优雅，取 1 更快结束递归。