LeetCode 77. 组合（Combinations）是一道非常经典的回溯算法模板题。题目要求返回范围 [1, n] 中所有可能的 k 个数的组合。
针对这道题，这里为你提供两种主流的 Python3 实现方案：
方法一：回溯法 + 剪枝优化（面试核心解法）
回溯法本质上是一种穷举，我们可以将搜索过程抽象为一棵树形结构。为了让算法更高效，我们需要引入剪枝操作：如果当前剩余的数字数量不足以凑齐 k 个数，就可以提前终止当前分支的搜索，从而大幅减少无效递归。
核心逻辑：
- 终止条件：当临时路径 path 的长度等于 k 时，说明找到了一个有效组合，将其加入结果集并返回。
- 单层搜索：从 start_index 开始遍历，通过剪枝公式 i <= n - (k - len(path)) + 1 控制循环边界。
- 回溯撤销：在递归返回后，必须将当前节点从 path 中弹出（path.pop()），恢复现场以便尝试其他分支。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
path = []
def backtrack(start_index: int): # 终止条件：组合长度达到 k if len(path) == k: # 注意：Python 中必须使用 copy() 或切片 [:] 进行硬拷贝 # 否则 result 中存储的只是 path 的引用，后续回溯会改变结果 result.append(path.copy()) return # 剪枝优化：剩余元素必须足够凑齐 k 个 # 剩余需要的元素个数 = k - len(path) # 当前 i 最大可以取到 n - (k - len(path)) + 1 max_start = n - (k - len(path)) + 1 for i in range(start_index, max_start + 1): path.append(i) # 处理节点：选择当前数字 backtrack(i + 1) # 递归：从下一个数字开始搜索 path.pop() # 回溯：撤销选择，恢复现场 backtrack(1) return result方法二：利用内置库 itertools（工程快捷解法）
在实际工程开发中，如果只需要快速得到结果，可以直接调用 Python 标准库中的 itertools.combinations 函数。它会在内部生成所有长度为 r 的子序列迭代器，我们只需将其转换为列表即可。
from typing import List
from itertools import combinations
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 生成 1 到 n 的列表，并获取长度为 k 的组合
# map(list, …) 用于将返回的元组格式转换为列表格式
return list(map(list, combinations(range(1, n + 1), k)))
面试建议：
- 如果在面试或算法考试中遇到此题，强烈建议手写方法一。这能向面试官充分展示你对递归、回溯状态恢复以及剪枝优化的深刻理解。
- 如果是在日常业务开发中，且对性能没有极端要求，方法二代码极其简洁，是提升开发效率的首选。
回溯法在刚接触时，状态恢复（path.pop()）和硬拷贝（path.copy()）往往是新手最容易踩坑的地方。如果你刚刷完颜色分类，可以对比一下回溯法中的“撤销选择”和双指针中的“指针移动”，它们其实都是在控制状态的变化。需要我帮你梳理几道同类型的回溯变体题（如组合总和、全排列）吗？
