概述回溯搜索题的核心套路学完递归之后我们继续学习一个非常重要的算法专题回溯算法。回溯可以理解为递归的一种典型应用。如果说递归关注的是“把问题拆成更小的同类问题”那么回溯更关注在一堆选择中不断尝试、深入、撤销再尝试下一种可能很多算法题看起来是在问所有排列有多少种所有组合有哪些所有子集有哪些有没有一条路径能走到终点棋盘上能不能放下若干个棋子这些题的共同点是需要枚举所有可能的选择过程。如果用暴力枚举硬写代码很容易混乱。而回溯算法提供了一套比较稳定的写法做选择 - 递归进入下一层 - 撤销选择这篇文章会围绕回溯最经典的三类题展开全排列组合子集学完这篇你应该能理解回溯的“路径、选择列表、终止条件”并能写出全排列、组合、子集三类基础题。核心概念回溯到底是什么回溯算法的本质是在搜索树上做深度优先遍历。每一次递归调用都是在搜索树中向下一层走。每一次递归返回都是从当前选择退回来尝试别的选择。比如从[1, 2, 3]中生成所有排列第一位可以选1 2 3如果第一位选了1第二位还可以选2 3如果第二位选了2第三位只能选3这个过程可以画成搜索树[] / | \ [1] [2] [3] / \ / \ / \ [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] | | | | | | [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]每一条从根节点到叶子节点的路径就是一个完整答案。回溯中的三个关键词路径当前已经做出的选择选择列表当前还能做哪些选择终止条件什么时候得到一个完整答案以全排列为例路径当前已经排列好的数字选择列表还没有使用过的数字终止条件路径长度等于数组长度回溯就是在搜索树中不断选择、递归、撤销选择直到枚举出所有可能答案。回溯模板先记住这段代码结构回溯题虽然变化很多但基础结构比较固定。voidbacktrack(路径,选择列表){if(满足结束条件){收集答案;return;}for(选择:选择列表){做选择;backtrack(路径,新的选择列表);撤销选择;}}这段模板里最重要的是三步做选择 递归 撤销选择比如path.add(nums[i]);backtrack(...);path.remove(path.size()-1);其中path.add(nums[i])表示做选择backtrack(...)表示进入下一层path.remove(path.size() - 1)表示撤销选择为什么必须撤销选择因为当前选择只属于当前这一条路径。当递归返回后程序要回到上一层继续尝试其他选择。如果不撤销后面的路径就会被前面的选择污染。回溯代码的灵魂是“做选择、递归、撤销选择”。例题一全排列题目给定一个不含重复数字的数组nums返回其所有可能的全排列。示例输入nums [1, 2, 3] 输出 [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]解题思路全排列的特点是每个数字都要用一次并且顺序不同算不同答案因此我们需要记录哪些数字已经使用过。常见做法是使用一个boolean[] used数组。函数定义backtrack(nums, used, path, ans)表示在当前path的基础上继续选择没有用过的数字生成完整排列。终止条件path.size() nums.length说明已经选满了一个排列。Java 代码实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegerpermute(int[]nums){ListListIntegeransnewArrayList();ListIntegerpathnewArrayList();boolean[]usednewboolean[nums.length];backtrack(nums,used,path,ans);returnans;}privatevoidbacktrack(int[]nums,boolean[]used,ListIntegerpath,ListListIntegerans){if(path.size()nums.length){ans.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i]){continue;}path.add(nums[i]);used[i]true;backtrack(nums,used,path,ans);used[i]false;path.remove(path.size()-1);}}}为什么要new ArrayList(path)收集答案时不能直接写ans.add(path);因为path是一个会不断变化的列表。后续递归中还会继续添加和删除元素。所以应该拷贝一份当前路径ans.add(newArrayList(path));这样保存到答案中的才是当前时刻的排列。执行过程以[1, 2, 3]为例选择 1 - 选择 2 - 选择 3 - 得到 [1,2,3] 撤销 3 - 尝试其他选择 撤销 2 - 选择 3 - 选择 2 - 得到 [1,3,2] 撤销 1 - 从 2 开始继续尝试复杂度分析时间复杂度O(n * n!)空间复杂度O(n)其中n!是排列数量每个答案复制时需要O(n)时间。空间复杂度这里不计算最终答案数组只计算递归栈和路径。全排列每一层都可以从所有未使用数字中选择一个所以需要used数组记录使用状态。例题二组合题目给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。示例输入n 4, k 2 输出 [ [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] ]组合和排列有什么区别排列关心顺序[1, 2] 和 [2, 1] 是不同排列组合不关心顺序[1, 2] 和 [2, 1] 是同一个组合所以组合题不能每一层都从头开始选。否则会产生重复答案。组合题通常需要一个start参数表示当前这一层从哪里开始选择。解题思路函数定义backtrack(start, n, k, path, ans)表示从start开始继续选择数字直到选出长度为k的组合。终止条件path.size() k递归选择范围for i from start to n递归进入下一层时下一次只能从i 1开始backtrack(i1,n,k,path,ans);这样就能避免重复选择之前的数字。Java 代码实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegercombine(intn,intk){ListListIntegeransnewArrayList();ListIntegerpathnewArrayList();backtrack(1,n,k,path,ans);returnans;}privatevoidbacktrack(intstart,intn,intk,ListIntegerpath,ListListIntegerans){if(path.size()k){ans.add(newArrayList(path));return;}for(intistart;in;i){path.add(i);backtrack(i1,n,k,path,ans);path.remove(path.size()-1);}}}为什么下一层从i 1开始假设当前选择了2那么后面只能选择比2更大的数字。这样可以保证每个组合只出现一次。例如[1, 2] 会被生成 [2, 1] 不会再被生成这正是组合题去重的关键。剪枝优化上面的代码可以继续优化。如果当前剩余数字数量已经不够凑出k个就没必要继续搜索。当前还需要选择k - path.size()从i到n一共有n - i 1个数字。所以i最大可以到n - (k - path.size()) 1优化代码privatevoidbacktrack(intstart,intn,intk,ListIntegerpath,ListListIntegerans){if(path.size()k){ans.add(newArrayList(path));return;}intneedk-path.size();intmaxStartn-need1;for(intistart;imaxStart;i){path.add(i);backtrack(i1,n,k,path,ans);path.remove(path.size()-1);}}复杂度分析时间复杂度O(k * C(n, k))空间复杂度O(k)其中C(n, k)是组合数量每个答案复制需要O(k)时间。组合题不关心顺序所以要用start控制下一层只能往后选。例题三子集题目给定一个不含重复元素的整数数组nums返回该数组所有可能的子集。示例输入nums [1, 2, 3] 输出 [ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] ]子集和组合的关系子集可以看成是所有长度的组合比如[1, 2, 3]的子集包括长度为0的组合[]长度为1的组合[1]、[2]、[3]长度为2的组合[1,2]、[1,3]、[2,3]长度为3的组合[1,2,3]所以子集题也需要start参数避免重复。解题思路子集题和组合题最大的区别是每一个路径本身都是一个答案组合题通常要等path.size() k才收集答案。而子集题每进入一层都可以先收集当前路径。函数定义backtrack(start, nums, path, ans)表示从start开始继续选择元素生成所有包含当前路径的子集。Java 代码实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegersubsets(int[]nums){ListListIntegeransnewArrayList();ListIntegerpathnewArrayList();backtrack(0,nums,path,ans);returnans;}privatevoidbacktrack(intstart,int[]nums,ListIntegerpath,ListListIntegerans){ans.add(newArrayList(path));for(intistart;inums.length;i){path.add(nums[i]);backtrack(i1,nums,path,ans);path.remove(path.size()-1);}}}执行过程以[1, 2, 3]为例初始路径 []收集 [] 选择 1收集 [1] 选择 2收集 [1,2] 选择 3收集 [1,2,3] 撤销 3撤销 2 选择 3收集 [1,3] 撤销 1 选择 2收集 [2] ...为什么不用显式终止条件子集题中下面这个循环自然会结束for(intistart;inums.length;i)当start nums.length时循环不会执行函数自然返回。所以子集题可以不写显式的if(startnums.length){return;}但如果你写上也不是错误只是没有必要。复杂度分析时间复杂度O(n * 2^n)空间复杂度O(n)长度为n的数组一共有2^n个子集每个子集复制最多需要O(n)时间。子集题中每个路径都是答案因此进入递归函数后先收集当前路径。三类题型对比排列、组合、子集怎么区分全排列、组合、子集都是回溯经典题但它们的搜索方式不同。题型是否关心顺序是否需要used是否需要start什么时候收集答案全排列关心需要不需要路径长度等于数组长度组合不关心通常不需要需要路径长度等于k子集不关心通常不需要需要每个路径都可以收集如何快速判断如果题目说返回所有可能的排列通常是全排列顺序不同算不同答案需要考虑used。如果题目说从 n 个数里选 k 个通常是组合不关心顺序需要start。如果题目说返回所有子集通常每个路径都能成为答案也需要start。排列看使用状态组合看起始位置子集每层都收集答案。剪枝让搜索少走无效分支回溯本质上是在枚举可能性。如果可能性很多搜索树会非常大。剪枝的作用是提前判断某些分支不可能得到答案直接跳过组合题中的剩余数量判断就是一种剪枝。例如intneedk-path.size();intmaxStartn-need1;如果后面的数字已经不够选了就不再进入那条分支。常见剪枝方式数量剪枝剩余元素不够直接停止条件剪枝当前路径已经不满足题目要求直接停止重复剪枝同一层跳过重复元素避免重复答案边界剪枝超过目标值、越界、冲突时停止不过初学阶段不要为了剪枝把代码写复杂。建议先写出正确的回溯模板再根据题目规模考虑优化。常见坑点回溯最容易错在哪里1. 忘记撤销选择错误示例path.add(nums[i]);backtrack(...);少了path.remove(path.size()-1);这样会导致后面的路径包含前面分支留下的元素。正确写法path.add(nums[i]);backtrack(...);path.remove(path.size()-1);2. 收集答案时没有复制路径错误写法ans.add(path);正确写法ans.add(newArrayList(path));原因是path会继续变化答案中必须保存当前路径的副本。3. 排列题忘记标记使用状态全排列中每个数字只能使用一次。如果没有used数组就可能重复使用同一个数字。正确流程used[i]true;backtrack(...);used[i]false;注意used[i] false也是撤销选择的一部分。4. 组合题没有使用start组合不关心顺序。如果每一层都从0开始遍历就会产生重复。例如[1, 2] [2, 1]对于组合题来说它们是同一个答案。所以组合题需要backtrack(i1,...);5. 终止条件写错排列题的终止条件通常是path.size()nums.length组合题的终止条件通常是path.size()k子集题通常一进函数就收集答案不一定需要显式终止条件。不同题型的终止条件不同不要混用模板。回溯和 DFS它们是什么关系很多人会把回溯和 DFS 混在一起。它们确实关系很近但关注点不完全一样。DFS强调搜索方式是深度优先地往下走回溯强调状态恢复是尝试选择后再撤销选择可以这样理解回溯通常是 DFS 的一种应用形式在排列、组合、子集这类题中我们使用 DFS 深入搜索树。同时每次返回上一层时要撤销当前选择。这就是回溯。DFS 负责往深处搜索回溯负责在搜索后恢复现场。模板总结三类经典回溯写法全排列模板voidbacktrack(int[]nums,boolean[]used,ListIntegerpath,ListListIntegerans){if(path.size()nums.length){ans.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i]){continue;}path.add(nums[i]);used[i]true;backtrack(nums,used,path,ans);used[i]false;path.remove(path.size()-1);}}组合模板voidbacktrack(intstart,intn,intk,ListIntegerpath,ListListIntegerans){if(path.size()k){ans.add(newArrayList(path));return;}for(intistart;in;i){path.add(i);backtrack(i1,n,k,path,ans);path.remove(path.size()-1);}}子集模板voidbacktrack(intstart,int[]nums,ListIntegerpath,ListListIntegerans){ans.add(newArrayList(path));for(intistart;inums.length;i){path.add(nums[i]);backtrack(i1,nums,path,ans);path.remove(path.size()-1);}}总结回溯算法看起来像是在“试错”但它并不是乱试。它是在一棵搜索树上有组织地枚举所有可能。你可以重点记住下面几句话回溯本质是搜索树上的深度优先遍历每一层递归都代表一次选择path保存当前路径for循环枚举当前层可选项做选择之后进入下一层递归递归返回后必须撤销选择收集答案时要复制当前路径排列通常用used组合和子集通常用start子集题每个路径都是答案剪枝可以减少无效搜索但先保证代码正确初学回溯时建议不要只背模板。每做一道题都先画出前两层搜索树再写代码。当你能看懂搜索树回溯代码就会变得很自然。