LeetCode-77. 组合 - sheep44044的小站

回溯#

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
输入：n = 4, k = 2
2
输出：
3
[
4
  [2,4],
5
  [3,4],
6
  [2,3],
7
  [1,2],
8
  [1,3],
9
  [1,4],
10
]

示例 2：

1
输入：n = 1, k = 1
2
输出：[[1]]

1
func combine(n int, k int) [][]int {
2
    res := [][]int{}
3
    path := []int{}
4

5
    var backtrack func(int)
6
    backtrack = func(index int) {
7
        if len(path) == k {
8
            res = append(res, append([]int(nil), path...))
9
            return
10
        }
11

12
        for i := index; i <= n; i++ {
13
            path = append(path, i)
14
            backtrack(i+1)
15
            path = path[:len(path)-1]
16
        }
17
    }
18

19
    backtrack(1)
20
    return res
21
}