力扣 77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
方案一：递归，遍历每一种可能。
func combine(n int, k int) (ans [][]int) {
// 当前选中的元素
chosen := make([]int, 0, k)
// 递归函数
var recur func(i int)
recur = func(i int) {
// 如果长度达到 k，则做 chosen 的深拷贝，将结果保存
if len(chosen) == k {
tmp := make([]int, k)
copy(tmp, chosen)
ans = append(ans, tmp)
return
}
// 如果余下的元素不足以满足 k 个数子的组合则直接返回
if len(chosen) + (n - i + 1) < k {
return
}
// 不选当前元素进行下一轮递归
recur(i + 1)
// 选择当前元素进行下一轮递归
chosen = append(chosen, i)
recur(i + 1)
// 还原现场，防止当前递归分支的变动影响到相邻分支
chosen = chosen[:len(chosen) - 1]
}
// 从元素 1 开始递归
recur(1)
return
}
- 时间复杂度：O(k * n!/(m! * (n - m)!))，因为一共有 n!/(m! * (n - m)!) 个状态，每个状态需要 O(k) 的时间复杂度（深拷贝），所以时间复杂度为 O(k * n!/(m! * (n - m)!))。
- 空间复杂度：O(k + n)，因为栈深度为 n，chosen 长度为 k ，所以空间复杂度为 O(n + k)。