leetcode 77. 组合

题目描述

给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。

示例:


输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

题解

回溯,每一个组合都是递逐渐增的

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func combine(n int, k int) [][]int {
res := make([][]int, 0)
backtrack(&res, n, 1, k, []int{})
return res
}

func backtrack(res *[][]int, n int, num int, k int, visit []int) {
if len(visit) == k {
tmp := make([]int, 0)
tmp = append(tmp, visit...)
*res = append(*res, tmp)
} else {
for i := num; i <= n; i++ {
visit = append(visit, i)
backtrack(res, n, i+1, k, visit)
visit = visit[:len(visit)-1]
}
}
}