【笔面试算法学习专栏】回溯算法·基础三题精讲（22.括号生成、46.全排列、78.子集）

引言回溯算法基础回溯算法是算法设计与面试中的核心考点它通过系统性地枚举所有可能候选解来寻找问题的解。当探索到某一步发现当前候选解不可能是解时就“回溯”返回尝试其他路径。回溯算法的本质是对解空间树的深度优先搜索DFS但通过剪枝函数避免无效搜索从而高效地求解组合、排列、子集、棋盘类等需要枚举的问题。回溯算法的核心特征系统性搜索按深度优先策略遍历解空间树状态回退当路径不满足约束时撤销选择返回上一层剪枝优化通过约束条件提前终止无效分支的搜索通用框架回溯算法的通用模板如下掌握这个框架是解决所有回溯问题的关键defbacktrack(path,choices):ifmeet_goal():# 满足结束条件result.append(path[:])# 深拷贝当前路径returnforchoiceinchoices:ifnotvalid(choice):# 约束检查continue# 剪枝make_choice(choice)# 做出选择backtrack(path,choices)# 递归探索undo_choice(choice)# 撤销选择回溯注回溯算法的时间复杂度通常是指数级的但通过巧妙的剪枝可以大幅减少实际搜索空间。在面试中不仅要写出正确解法还要能够分析时间/空间复杂度并提出优化思路。本文选取力扣hot100中三道经典回溯题目括号生成、全排列、子集通过深度解析帮助读者掌握回溯算法的通用解题框架理解不同问题背景下状态管理的技巧学会分析时间/空间复杂度积累面试常见考点与避坑指南一、22.括号生成1.1 题目概述与链接题目链接力扣22. 括号生成问题描述给定数字n生成所有可能的有效括号组合。有效括号组合需满足左括号和右括号数量相等均为n任意前缀中左括号数量不少于右括号数量示例输入: n 3 输出: [((())),(()()),(())(),()(()),()()()]1.2 核心解题思路括号生成问题本质是构造长度为2n的字符串每个位置可以选择左括号(或右括号)但需要满足上述两个约束条件。回溯算法的设计要点选择列表每个位置可选择(或)约束条件左括号数量left不能超过n右括号数量right不能超过左括号数量left结束条件字符串长度达到2n时得到一个有效解关键洞察在递归过程中维护当前左括号和右括号的计数确保右括号不会在左括号之前出现即保证任意前缀中左括号不少于右括号。1.3 时间复杂度与空间复杂度分析时间复杂度O ( 4 n n ) O(\frac{4^n}{\sqrt{n}})O(n​4n​)推导过程解空间树有2 2 n 4 n 2^{2n} 4^n22n4n个叶子节点但通过剪枝减少了大量无效搜索。卡特兰数C n 1 n 1 ( 2 n n ) ∼ 4 n π n 3 / 2 C_n \frac{1}{n1} \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n^{3/2}}}Cn​n11​(n2n​)∼πn3/2​4n​给出了有效括号组合的数量因此时间复杂度与卡特兰数成正比为O ( 4 n n ) O(\frac{4^n}{\sqrt{n}})O(n​4n​)。空间复杂度O ( n ) O(n)O(n)递归深度为2 n 2n2n每层递归需要常数空间存储局部变量。结果列表存储所有有效组合但空间复杂度分析通常不考虑输出占用的空间因此主要考虑递归栈空间O ( n ) O(n)O(n)。1.4 Python代码实现fromtypingimportListclassSolution:defgenerateParenthesis(self,n:int)-List[str]:result[]defbacktrack(s:str,left:int,right:int): s: 当前构建的字符串 left: 已使用的左括号数量 right: 已使用的右括号数量 # 结束条件字符串长度达到2niflen(s)2*n:result.append(s)return# 选择1添加左括号如果还有左括号可用ifleftn:backtrack(s(,left1,right)# 选择2添加右括号如果右括号数量小于左括号数量ifrightleft:backtrack(s),left,right1)backtrack(,0,0)returnresult# 测试代码if__name____main__:solSolution()print(sol.generateParenthesis(3))# 输出[((())), (()()), (())(), ()(()), ()()()]代码解析backtrack函数维护当前字符串s和左右括号计数左括号添加条件left n确保不超过 n 个左括号右括号添加条件right left确保任意前缀中左括号不少于右括号递归终止条件字符串长度达到2n时记录结果关键代码行数15行符合≤20行要求1.5 优化思路与变式讨论优化思路字符串构建优化使用列表存储字符最后通过.join()拼接避免字符串拼接产生新对象迭代法可以使用栈模拟递归过程减少函数调用开销动态规划基于卡特兰数的递推关系dp[i]表示 i 对括号的所有组合变式讨论生成所有可能的括号序列不要求有效去掉约束条件简单回溯判断单个括号序列是否有效使用栈或计数器不同括号类型{}[]()混合增加状态记录不同类型括号的匹配情况1.6 面试考点与注意事项常见考点理解括号有效性约束的数学本质卡特兰数设计递归函数参数与状态管理分析时间复杂度的推导过程提出优化方案如字符串构建优化注意事项避免重复计算不同路径可能生成相同字符串但本题由于约束条件不会重复剪枝条件顺序先添加左括号再添加右括号符合自然构造顺序全局变量使用合理使用闭包或类变量存储结果避免参数传递复杂化二、46.全排列2.1 题目概述与链接题目链接力扣46. 全排列问题描述给定一个不含重复数字的整数数组nums返回所有可能的全排列。你可以按任意顺序返回答案。示例输入: nums [1,2,3] 输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]2.2 核心解题思路全排列问题要求生成数组元素的所有可能排列。回溯算法的设计要点选择列表当前可选的元素集合尚未使用的元素约束条件每个元素只能使用一次结束条件当前排列长度等于原数组长度两种实现方法基于标记数组visited使用布尔数组记录每个元素是否已使用基于交换swap通过交换元素位置实现原地排列2.3 时间复杂度与空间复杂度分析时间复杂度O ( n ! ) O(n!)O(n!)推导过程对于 n 个元素的全排列共有n ! n!n!种排列。回溯算法会生成所有排列因此时间复杂度为O ( n ! ) O(n!)O(n!)。更精确地考虑递归树的节点数根节点 1 个第一层 n 个第二层 n(n-1) 个…总节点数为1 n n ( n − 1 ) . . . n ! 1 n n(n-1) ... n!1nn(n−1)...n!但主要项为n ! n!n!。空间复杂度O ( n ) O(n)O(n)递归深度为 n每层递归需要常数空间。标记数组需要O ( n ) O(n)O(n)空间。结果列表存储所有排列但通常不计入空间复杂度。2.4 Python代码实现方法一基于标记数组推荐直观易懂fromtypingimportListclassSolution:defpermute(self,nums:List[int])-List[List[int]]:result[]nlen(nums)visited[False]*ndefbacktrack(path:List[int]):# 结束条件路径长度等于数组长度iflen(path)n:result.append(path[:])# 深拷贝returnforiinrange(n):ifvisited[i]:continue# 已使用跳过# 做出选择visited[i]Truepath.append(nums[i])# 递归探索backtrack(path)# 撤销选择path.pop()visited[i]Falsebacktrack([])returnresult方法二基于交换原地操作节省空间fromtypingimportListclassSolution:defpermute(self,nums:List[int])-List[List[int]]:result[]defbacktrack(first:int): first: 当前需要固定位置的索引 # 结束条件所有位置都已固定iffirstlen(nums):result.append(nums[:])# 记录当前排列return# 将 first 位置与后续每个位置交换foriinrange(first,len(nums)):# 交换元素nums[first],nums[i]nums[i],nums[first]# 递归固定下一个位置backtrack(first1)# 撤销交换回溯nums[first],nums[i]nums[i],nums[first]backtrack(0)returnresult代码解析方法一使用visited数组记录元素使用状态适合理解回溯的状态管理方法二通过交换实现原地排列节省了标记数组的空间关键代码行数方法一 19行方法二 16行均符合≤20行要求注意列表的深拷贝path[:]和nums[:]确保记录当前状态快照2.5 优化思路与变式讨论优化思路剪枝优化对于含重复元素的全排列需要跳过重复选择迭代实现使用堆算法Heap’s algorithm生成全排列记忆化搜索对于大规模问题可缓存子问题结果变式讨论含重复元素的全排列力扣47题需要额外去重逻辑下一个排列力扣31题给定排列求字典序下一个排列排列序列力扣60题求第 k 个排列部分排列从 n 个元素中取 k 个进行排列2.6 面试考点与注意事项常见考点比较两种实现方法的优劣标记数组 vs 交换处理含重复元素的全排列的去重技巧分析递归树的时间复杂度实现迭代版本的全排列算法注意事项状态恢复递归返回后必须恢复现场标记复位、交换还原深拷贝必要性直接添加path会因引用导致结果被修改递归终止条件确保路径长度等于数组长度而不是索引越界去重策略对于重复元素需要排序后跳过相同元素三、78.子集3.1 题目概述与链接题目链接力扣78. 子集问题描述给定一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集你可以按任意顺序返回答案。示例输入: nums [1,2,3] 输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]3.2 核心解题思路子集问题要求生成集合的所有子集。回溯算法的设计要点选择列表当前位置可选的元素从当前索引开始约束条件无特殊约束但为避免重复每个元素只能考虑一次按顺序选择结束条件遍历完所有元素两种经典解法基于回溯的深度优先搜索标准回溯框架记录所有路径基于位运算的枚举利用二进制掩码表示元素选择状态3.3 时间复杂度与空间复杂度分析时间复杂度O ( 2 n ) O(2^n)O(2n)推导过程对于 n 个元素的集合共有2 n 2^n2n个子集。回溯算法会生成所有子集因此时间复杂度为O ( 2 n ) O(2^n)O(2n)。更精确地递归树的节点数为2 n 1 − 1 2^{n1} - 12n1−1即O ( 2 n ) O(2^n)O(2n)。空间复杂度O ( n ) O(n)O(n)递归深度为 n每层递归需要常数空间。结果列表存储所有子集但通常不计入空间复杂度。3.4 Python代码实现方法一基于回溯标准解法fromtypingimportListclassSolution:defsubsets(self,nums:List[int])-List[List[int]]:result[]nlen(nums)defbacktrack(start:int,path:List[int]): start: 当前可选的起始索引 path: 当前已选择的元素列表 # 记录当前路径所有路径都是有效子集result.append(path[:])# 遍历可选元素foriinrange(start,n):# 做出选择path.append(nums[i])# 递归探索从下一个位置开始backtrack(i1,path)# 撤销选择path.pop()backtrack(0,[])returnresult方法二基于位运算巧妙枚举fromtypingimportListclassSolution:defsubsets(self,nums:List[int])-List[List[int]]:result[]nlen(nums)# 遍历所有二进制掩码 (0 到 2^n - 1)formaskinrange(1n):subset[]# 检查掩码的每一位foriinrange(n):ifmask(1i):# 第i位为1表示选择nums[i]subset.append(nums[i])result.append(subset)returnresult代码解析方法一使用标准回溯框架start参数确保每个元素只考虑一次避免重复方法二利用二进制数的特性n 位二进制数正好对应2 n 2^n2n个子集关键代码行数方法一 15行方法二 12行均符合≤20行要求注意方法一中每次递归都记录当前路径而不是等到路径结束3.5 优化思路与变式讨论优化思路迭代法从空集开始逐个添加元素生成所有子集字典序生成按照特定顺序生成子集便于处理剪枝优化对于子集大小有限制的问题提前终止变式讨论含重复元素的子集力扣90题需要去重处理子集大小限制只生成大小为 k 的子集子集和问题找到和为特定值的子集最大子集满足特定条件的最大子集3.6 面试考点与注意事项常见考点理解子集问题的本质组合数学中的幂集掌握回溯与位运算两种解法的转换分析递归树的时间复杂度推导处理含重复元素的子集去重注意事项空集包含子集问题必须包含空集顺序无关性[1,2]和[2,1]是同一子集需要避免重复结果顺序通常不要求特定顺序但面试官可能询问生成顺序大数处理当 n 较大时2 n 2^n2n会非常大需要评估可行性总结与扩展回溯算法解题框架归纳通过三道经典题目的解析我们可以总结出回溯算法的通用解题步骤定义状态确定递归函数的参数当前路径、可用选择、辅助状态设计选择明确每一步可做的选择集合设定约束添加剪枝条件提前终止无效分支确定目标定义递归终止条件记录有效解状态回退递归返回后恢复现场确保不影响后续搜索时间复杂度分析技巧回溯算法的时间复杂度分析通常遵循以下模式确定解空间树的大小叶子节点数考虑剪枝减少的搜索空间用渐进符号表示通常为指数级O ( c n ) O(c^n)O(cn)或阶乘级O ( n ! ) O(n!)O(n!)力扣回溯经典题目推荐组合类问题17.电话号码的字母组合39.组合总和40.组合总和 II77.组合排列类问题47.全排列 II含重复元素60.排列序列31.下一个排列子集类问题90.子集 II含重复元素491.递增子序列棋盘类问题51.N皇后37.解数独面试准备建议掌握模板熟记回溯通用框架能够快速套用理解本质明白回溯是DFS剪枝理解状态树结构熟练分析能够推导时间/空间复杂度积累变式熟悉常见变式问题的处理技巧代码规范注意深拷贝、状态恢复等细节最后思考回溯算法虽然概念上简单但在实际面试中往往需要结合具体问题灵活调整。通过这三道基础题目的精讲希望读者能够建立扎实的回溯算法基础在面试中遇到更复杂的回溯变式时能够快速识别问题本质设计出高效的解法。记住回溯算法的核心是探索所有可能性但通过巧妙的剪枝大幅减少搜索空间。掌握这一平衡艺术是算法能力提升的关键。