LeetCode 77. 组合Combinations是一道非常经典的回溯算法模板题。题目要求返回范围 [1, n] 中所有可能的 k 个数的组合。针对这道题这里为你提供两种主流的 Python3 实现方案方法一回溯法 剪枝优化面试核心解法回溯法本质上是一种穷举我们可以将搜索过程抽象为一棵树形结构。为了让算法更高效我们需要引入剪枝操作如果当前剩余的数字数量不足以凑齐 k 个数就可以提前终止当前分支的搜索从而大幅减少无效递归。核心逻辑终止条件当临时路径 path 的长度等于 k 时说明找到了一个有效组合将其加入结果集并返回。单层搜索从 start_index 开始遍历通过剪枝公式 i n - (k - len(path)) 1 控制循环边界。回溯撤销在递归返回后必须将当前节点从 path 中弹出path.pop()恢复现场以便尝试其他分支。from typing import Listclass 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 Listfrom itertools import combinationsclass 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()往往是新手最容易踩坑的地方。如果你刚刷完颜色分类可以对比一下回溯法中的“撤销选择”和双指针中的“指针移动”它们其实都是在控制状态的变化。需要我帮你梳理几道同类型的回溯变体题如组合总和、全排列吗