第17篇-回溯算法基础-全排列-组合-子集问题通关

概述：回溯搜索题的核心套路

学完递归之后，我们继续学习一个非常重要的算法专题：回溯算法。

回溯可以理解为递归的一种典型应用。
如果说递归关注的是“把问题拆成更小的同类问题”，那么回溯更关注：

在一堆选择中，不断尝试、深入、撤销，再尝试下一种可能

很多算法题看起来是在问：

• 所有排列有多少种？
• 所有组合有哪些？
• 所有子集有哪些？
• 有没有一条路径能走到终点？
• 棋盘上能不能放下若干个棋子？

这些题的共同点是：需要枚举所有可能的选择过程。

如果用暴力枚举硬写，代码很容易混乱。
而回溯算法提供了一套比较稳定的写法：

做选择 -> 递归进入下一层 -> 撤销选择

这篇文章会围绕回溯最经典的三类题展开：

1. 全排列
2. 组合
3. 子集

学完这篇，你应该能理解回溯的“路径、选择列表、终止条件”，并能写出全排列、组合、子集三类基础题。

核心概念：回溯到底是什么

回溯算法的本质是：在搜索树上做深度优先遍历。

每一次递归调用，都是在搜索树中向下一层走。
每一次递归返回，都是从当前选择退回来，尝试别的选择。

比如从[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{publicList<List<Integer>>permute(int[]nums){List<List<Integer>>ans=newArrayList<>();List<Integer>path=newArrayList<>();boolean[]used=newboolean[nums.length];backtrack(nums,used,path,ans);returnans;}privatevoidbacktrack(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>ans){if(path.size()==nums.length){ans.add(newArrayList<>(path));return;}for(inti=0;i<nums.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(i+1,n,k,path,ans);

这样就能避免重复选择之前的数字。

Java 代码实现

importjava.util.ArrayList;importjava.util.List;classSolution{publicList<List<Integer>>combine(intn,intk){List<List<Integer>>ans=newArrayList<>();List<Integer>path=newArrayList<>();backtrack(1,n,k,path,ans);returnans;}privatevoidbacktrack(intstart,intn,intk,List<Integer>path,List<List<Integer>>ans){if(path.size()==k){ans.add(newArrayList<>(path));return;}for(inti=start;i<=n;i++){path.add(i);backtrack(i+1,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,List<Integer>path,List<List<Integer>>ans){if(path.size()==k){ans.add(newArrayList<>(path));return;}intneed=k-path.size();intmaxStart=n-need+1;for(inti=start;i<=maxStart;i++){path.add(i);backtrack(i+1,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{publicList<List<Integer>>subsets(int[]nums){List<List<Integer>>ans=newArrayList<>();List<Integer>path=newArrayList<>();backtrack(0,nums,path,ans);returnans;}privatevoidbacktrack(intstart,int[]nums,List<Integer>path,List<List<Integer>>ans){ans.add(newArrayList<>(path));for(inti=start;i<nums.length;i++){path.add(nums[i]);backtrack(i+1,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(inti=start;i<nums.length;i++)

当start == nums.length时，循环不会执行，函数自然返回。

所以子集题可以不写显式的：

if(start==nums.length){return;}

但如果你写上，也不是错误，只是没有必要。

复杂度分析

• 时间复杂度：O(n * 2^n)
• 空间复杂度：O(n)

长度为n的数组一共有2^n个子集，每个子集复制最多需要O(n)时间。

子集题中每个路径都是答案，因此进入递归函数后先收集当前路径。

三类题型对比：排列、组合、子集怎么区分

全排列、组合、子集都是回溯经典题，但它们的搜索方式不同。

如何快速判断

如果题目说：

返回所有可能的排列

通常是全排列，顺序不同算不同答案，需要考虑used。

如果题目说：

从 n 个数里选 k 个

通常是组合，不关心顺序，需要start。

如果题目说：

返回所有子集

通常每个路径都能成为答案，也需要start。

排列看使用状态，组合看起始位置，子集每层都收集答案。

剪枝：让搜索少走无效分支

回溯本质上是在枚举可能性。
如果可能性很多，搜索树会非常大。

剪枝的作用是：

提前判断某些分支不可能得到答案，直接跳过

组合题中的剩余数量判断就是一种剪枝。

例如：

intneed=k-path.size();intmaxStart=n-need+1;

如果后面的数字已经不够选了，就不再进入那条分支。

常见剪枝方式

• 数量剪枝：剩余元素不够，直接停止
• 条件剪枝：当前路径已经不满足题目要求，直接停止
• 重复剪枝：同一层跳过重复元素，避免重复答案
• 边界剪枝：超过目标值、越界、冲突时停止

不过初学阶段不要为了剪枝把代码写复杂。
建议先写出正确的回溯模板，再根据题目规模考虑优化。

常见坑点：回溯最容易错在哪里

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(i+1,...);

5. 终止条件写错

排列题的终止条件通常是：

path.size()==nums.length

组合题的终止条件通常是：

path.size()==k

子集题通常一进函数就收集答案，不一定需要显式终止条件。

不同题型的终止条件不同，不要混用模板。

回溯和 DFS：它们是什么关系

很多人会把回溯和 DFS 混在一起。
它们确实关系很近，但关注点不完全一样。

• DFS：强调搜索方式，是深度优先地往下走
• 回溯：强调状态恢复，是尝试选择后再撤销选择

可以这样理解：

回溯通常是 DFS 的一种应用形式

在排列、组合、子集这类题中，我们使用 DFS 深入搜索树。
同时每次返回上一层时，要撤销当前选择。
这就是回溯。

DFS 负责往深处搜索，回溯负责在搜索后恢复现场。

模板总结：三类经典回溯写法

全排列模板

voidbacktrack(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>ans){if(path.size()==nums.length){ans.add(newArrayList<>(path));return;}for(inti=0;i<nums.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,List<Integer>path,List<List<Integer>>ans){if(path.size()==k){ans.add(newArrayList<>(path));return;}for(inti=start;i<=n;i++){path.add(i);backtrack(i+1,n,k,path,ans);path.remove(path.size()-1);}}

子集模板

voidbacktrack(intstart,int[]nums,List<Integer>path,List<List<Integer>>ans){ans.add(newArrayList<>(path));for(inti=start;i<nums.length;i++){path.add(nums[i]);backtrack(i+1,nums,path,ans);path.remove(path.size()-1);}}

总结

回溯算法看起来像是在“试错”，但它并不是乱试。
它是在一棵搜索树上有组织地枚举所有可能。

你可以重点记住下面几句话：

• 回溯本质是搜索树上的深度优先遍历
• 每一层递归都代表一次选择
• path保存当前路径
• for循环枚举当前层可选项
• 做选择之后进入下一层递归
• 递归返回后必须撤销选择
• 收集答案时要复制当前路径
• 排列通常用used，组合和子集通常用start
• 子集题每个路径都是答案
• 剪枝可以减少无效搜索，但先保证代码正确

初学回溯时，建议不要只背模板。
每做一道题，都先画出前两层搜索树，再写代码。
当你能看懂搜索树，回溯代码就会变得很自然。