AI summary
type
status
date
slug
summary
category
tags
icon
password
虽然排列、组合、子集系列问题是高中就学过的，但如果想编写算法解决它们，还是非常考验计算机思维的，本文就讲讲编程解决这几个问题的核心思路，以后再有什么变体，你也能手到擒来，以不变应万变。
无论是排列、组合还是子集问题，简单说无非就是让你从序列
nums 中以给定规则取若干元素，主要有以下几种变体：形式一、元素无重不可复选，即
nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。以组合为例，如果输入
nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。形式二、元素可重不可复选，即
nums 中的元素可以存在重复，每个元素最多只能被使用一次。以组合为例，如果输入
nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。形式三、元素无重可复选，即
nums 中的元素都是唯一的，每个元素可以被使用若干次。以组合为例，如果输入
nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。当然，也可以说有第四种形式，即元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。
上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。
除此之外，题目也可以再添加各种限制条件，比如让你求和为
target 且元素个数为 k 的组合，那这么一来又可以衍生出一堆变体，怪不得面试笔试中经常考到排列组合这种基本题型。但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。
具体来说，你需要先阅读并理解前文 回溯算法套路框架，然后记住如下子集问题和排列问题的回溯树，就可以解决所有排列组合子集相关的问题：
为什么只要记住这两种树形结构就能解决所有相关问题呢？
首先，组合问题和子集问题其实是等价的，这个后面会讲；至于之前说的三种变化形式，无非是在这两棵树上剪掉或者增加一些树枝罢了。
那么，接下来我们就开始穷举，把排列/组合/子集问题的 9 种形式都过一遍，学学如何用回溯算法把它们一套带走。
子集（元素无重不可复选）
78. 子集
题目给你输入一个无重复元素的数组nums，其中每个元素最多使用一次，请你返回nums的所有子集。
好，我们暂时不考虑如何用代码实现，先回忆一下我们的高中知识，如何手推所有子集？
整个推导过程就是这样一棵树：
为什么集合
[2] 只需要添加 3，而不添加前面的 1 呢？因为集合中的元素不用考虑顺序，
[1,2,3] 中 2 后面只有 3，如果你添加了前面的 1，那么 [2,1] 会和之前已经生成的子集 [1,2] 重复。换句话说，我们通过保证元素之间的相对顺序不变来防止出现重复的子集。
注意这棵树的特性：
如果把根节点作为第 0 层，将每个节点和根节点之间树枝上的元素作为该节点的值，那么第
n 层的所有节点就是大小为 n 的所有子集。那么再进一步，如果想计算所有子集，那只要遍历这棵多叉树，把所有节点的值收集起来不就行了？
直接看代码：
backtrack 函数开头看似没有 base case，会不会进入无限递归？其实不会的，当
start == nums.length 时，叶子节点的值会被装入 res，但 for 循环不会执行，也就结束了递归。组合（元素无重不可复选）
如果你能够成功的生成所有无重子集，那么你稍微改改代码就能生成所有无重组合了。
你比如说，让你在
nums = [1,2,3] 中拿 2 个元素形成所有的组合，你怎么做？稍微想想就会发现，大小为 2 的所有组合，不就是所有大小为 2 的子集嘛。
所以我说组合和子集是一样的：大小为
k 的组合就是大小为 k 的子集。77. 组合
给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
还是以
nums = [1,2,3] 为例，刚才让你求所有子集，就是把所有节点的值都收集起来；现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合。反映到代码上，只需要稍改 base case，控制算法仅仅收集第
k 层节点的值即可：排列（元素无重不可复选）
排列问题在前文 回溯算法套路框架 讲过，这里就简单过一下。
力扣第 46 题「全排列」就是标准的排列问题：
给定一个不含重复数字的数组
nums，返回其所有可能的全排列。刚才讲的组合/子集问题使用
start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。但排列问题本身就是让你穷举元素的位置，
nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择。直接看代码：
这样，全排列问题就解决了。
但如果题目不让你算全排列，而是让你算元素个数为
k 的排列，怎么算？也很简单，改下
backtrack 函数的 base case，仅收集第 k 层的节点值即可。子集/组合（元素可重不可复选）
刚才讲的标准子集问题输入的
nums 是没有重复元素的，但如果存在重复元素，怎么处理呢？90. 子集 II
给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集。
当然，按道理说「集合」不应该包含重复元素的，但既然题目这样问了，我们就忽略这个细节吧，仔细思考一下这道题怎么做才是正事。
就以
nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：
你可以看到，
[2] 和 [1,2] 这两个结果出现了重复，所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历。体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现
nums[i] == nums[i-1]，则跳过：这段代码和之前标准的子集问题的代码几乎相同，就是添加了排序和剪枝的逻辑。
至于为什么要这样剪枝，结合前面的图应该也很容易理解，这样带重复元素的子集问题也解决了。
我们说了组合问题和子集问题是等价的，所以我们直接看一道组合的题目吧。
40. 组合总和 II
给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。
说这是一个组合问题，其实换个问法就变成子集问题了：请你计算
candidates 中所有和为 target 的子集。所以这题怎么做呢？
对比子集问题的解法，只要额外用一个
trackSum 变量记录回溯路径上的元素和，然后将 base case 改一改即可解决这道题：排列（元素可重不可复选）
排列问题的输入如果存在重复，比子集/组合问题稍微复杂一点。
47. 全排列 II
给定一个可包含重复数字的序列nums，按任意顺序 返回所有不重复的全排列。
先看解法代码：
- 对
nums进行了排序。
- 添加了一句额外的剪枝逻辑。
类比输入包含重复元素的子集/组合问题，你大概应该理解这么做是为了防止出现重复结果。
但是注意排列问题的剪枝逻辑，和子集/组合问题的剪枝逻辑略有不同：新增了
!used[i - 1] 的逻辑判断。这个地方理解起来就需要一些技巧性了，且听我慢慢到来。为了方便研究，依然把相同的元素用上标
' 以示区别。比如
[1,2,2'] 和 [1,2',2] 应该只被算作同一个排列，但被算作了两个不同的排列。所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？
答案是，保证相同元素在排列中的相对位置保持不变。
比如说
nums = [1,2,2'] 这个例子，我保持排列中 2 一直在 2' 前面。这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：
[ [1,2,2'],[2,1,2'],[2,2',1] ]，也就是正确答案。仔细思考，应该很容易明白其中的原理：
标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
这里拓展一下，如果你把上述剪枝逻辑中的
!used[i - 1] 改成 used[i - 1]，其实也可以通过所有测试用例，但效率会有所下降，这是为什么呢？之所以这样修改不会产生错误，是因为这种写法相当于维护了
2'' -> 2' -> 2 的相对顺序，最终也可以实现去重的效果。但为什么这样写效率会下降呢？因为这个写法剪掉的树枝不够多。
比如输入
nums = [2,2',2'']，如果用绿色树枝代表 backtrack 函数遍历过的路径，红色树枝代表剪枝逻辑的触发，那么 !used[i - 1] 这种剪枝逻辑得到的回溯树长这样：
而
used[i - 1] 这种剪枝逻辑得到的回溯树如下：
当然，关于排列去重，也有读者提出别的剪枝思路：
这个思路也是对的，设想一个节点出现了相同的树枝：
如果不作处理，这些相同树枝下面的子树也会长得一模一样，所以会出现重复的排列。
因为排序之后所有相等的元素都挨在一起，所以只要用
prevNum 记录前一条树枝的值，就可以避免遍历值相同的树枝，从而避免产生相同的子树，最终避免出现重复的排列。好了，这样包含重复输入的排列问题也解决了。
子集/组合（元素无重可复选）
终于到了最后一种类型了：输入数组无重复元素，但每个元素可以被无限次使用。
39. 组合总和
给你一个无重复元素的整数数组candidates和一个目标和target，找出candidates中可以使数字和为目标数target的所有组合。candidates中的每个数字可以无限制重复被选取。
这道题说是组合问题，实际上也是子集问题：
candidates 的哪些子集的和为 target？想解决这种类型的问题，也得回到回溯树上，我们不妨先思考思考，标准的子集/组合问题是如何保证不重复使用元素的？
答案在于
backtrack 递归时输入的参数 start 。这个 i 从 start 开始，那么下一层回溯树就是从 start + 1 开始，从而保证 nums[start] 这个元素不会被重复使用。那么反过来，如果我想让每个元素被重复使用，我只要把
i + 1 改成 i 即可：这相当于给之前的回溯树添加了一条树枝，在遍历这棵树的过程中，一个元素可以被无限次使用：
当然，这样这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的 base case 以结束算法，即路径和大于
target 时就没必要再遍历下去了。这道题的解法代码如下：
排列（元素无重可复选）
力扣上没有题目直接考察这个场景，我们不妨先想一下，
nums 数组中的元素无重复且可复选的情况下，会有哪些排列？比如输入
nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种。标准的全排列算法利用
used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。那这个问题就太简单了，不会考，这里略了。
至此，排列/组合/子集问题的九种变化就都讲完了。
只要从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决，这也是我强调树类型题目重要性的原因。