组合
Combinations
本机进度仅保存在当前浏览器
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合，顺序任意。
示例：n = 4，k = 2，输出 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]。
解题思路
- 子集模板的直接应用：从 1..n 中选，路径长度到 k 即收集。
- 剪枝是本题的考察点：剩余可选元素数量不足以凑满 k 个时提前返回，即 i <= n - (k - len(path)) + 1。
- 剪枝不影响正确性，只砍掉注定失败的分支，对 n、k 接近时收益显著。
参考实现
查看参考实现Python · 建议先自行作答
def combine(n, k):
res, path = [], []
def backtrack(start):
if len(path) == k:
res.append(path[:])
return
# 剪枝：剩余元素不够凑满 k 个时不再展开
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1)
path.pop()
backtrack(1)
return res