leetcode.77 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
背后数学描述无需多言。首先找个简单例子枚举所有组合，例如:4, 2 所有可能为(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)。可以看出具有很明显的树状结构，那就可以先画一颗树的草图，如下。
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 {
ans := [][]int{} // 记录答案
cur := []int{} //记录当前个数
var dfs func(int, int)
dfs = func(index int, depth int) {
// 递归深度为k
if len(cur) == k {
ans = append(ans, append([]int{}, cur...)) // 注意此处appen写法，详见golang slice扩容细节
return
}
for j := index+1; j <= n - depth + 1; j++ { // 这里实际上进行了剪枝，看图比较直观
cur = append(cur, j)
dfs(j, depth-1)
cur = cur[0: len(cur) - 1] //回溯
}
}
dfs(0, k)
return ans
}
|