- 组合
已解答
中等
相关标签
相关企业
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n
回溯的思路， 转化为树型来理解， 参数不确定可以后续补充
固定的模板
id backtraking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
func combine(n int, k int) [][]int {
var res [][]int
var trace []int
var backtrace func(k int, start int)
backtrace = func(k, start int) {
if k == 0 {
res = append(res, append([]int{}, trace...))
return
}
if start == n {
return
}
for i := start; i < n; i++ {
trace = append(trace, i+1)
backtrace(k-1, i+1)
trace = trace[:len(trace)-1]
}
}
backtrace(k, 0)
return res
}