Description

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

给出两个整数n和k，输出所有包含k个数字的组合，数字范围1..n。

Solution

224 ms, faster than 97.50%

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func combine(n int, k int) [][]int {
    result := [][]int{}

    // C(n, k)
    minK := k
    if n-k < minK {
        minK = n - k
    }
    p, c := 1, 1
    for i := 0; i < minK; i++ {
        c *= minK - i
        p *= n - i
    }
    c = p / c

    // 一次性申请内存，+k额外用于递归时存放
    memo := make([]int, c*k+k)

    // 前面k个用于递归时使用，结果从第k+1个开始
    start := k

    var solve func(n, kk int)
    solve = func(it, kk int) {
        if kk == k-1 {
            for it < n {
                it++
                memo[kk] = it

                r := memo[start : start+k]
                copy(r, memo)
                result = append(result, r)

                start += k
            }
        } else {
            for it < n {
                it++
                memo[kk] = it
                solve(it, kk+1)
            }
        }
    }

    solve(0, 0)

    return result
}