在 回溯算法理论基础 中我们详细的介绍了回溯算法的理论知识，不同于教科书般的讲解，这里介绍的回溯法的效率，解决的问题以及模板都是在刷题的过程中非常实用！

回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 棋盘问题：N皇后，解数独等等

我在回溯算法系列讲解中就按照这个顺序给大家讲解，可以说深入浅出，步步到位。

回溯法确实不好理解，所以需要把回溯法抽象为一个图形来理解就容易多了，在后面的每一道回溯法的题目我都将遍历过程抽象为树形结构方便大家的理解。

在 回溯算法理论基础 中，我还用了回溯三部曲来分析回溯算法，并给出了回溯法的模板：

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

事实证明这个模板会伴随整个回溯法系列！

题目回顾

下面我们回顾一下回溯法系列做过的题。

1、组合问题

77. 组合

题目：从 [ 1, n ] 这 n 个数中选 k 个数的组合，有多少种方法？

77. 组合 这道题就是标准的回溯法模板题。

需要注意的是，组合是不强调顺序的，即 1,2 和 2,1 都会被认为是同一种组合，所以要避免重复选择元素。

直接的解法当然是使用 for 循环，k 为几就套几层 for 循环。

举个例子，若 k = 2，n = 5，代码如下：

  1. int n = 5;
  2. for (int i = 1; i <= n; i++) {
  3.     // i + 1 是关键，结合下面的输出，好好体会一下
  4.     for (int j = i + 1; j <= n; j++) {
  5.         System.out.println(i + " " + j);
  6.     }
  7. }

输出：

  1. 1 2
  2. 1 3
  3. 1 4
  4. 1 5
  5. 2 3
  6. 2 4
  7. 2 5
  8. 3 4
  9. 3 5
  10. 4 5

如果 n 为 100 ，k 为 50 呢，难道要手写 50 层 for 循环吗？显然这不现实，即使你想这么干，但 k 也是一个题目输入的变量，而不是常量。

我们就可以用回溯法来解决嵌套层数的问题。因为回溯法是用递归来做层叠嵌套的（可以理解是开 k 层 for 循环），每一次的递归中嵌套一个 for 循环，那么递归就可以用于解决多层嵌套循环的问题了。

本题也是可以剪枝的，具体细节可以看一下完整题解：77. 组合

216. 组合总和III

题目：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

还是要强调一遍，组合是不强调顺序的，即 1,2 和 2,1 都会被认为是同一种组合，所以要避免重复选择元素。

我们刚做过的 77. 组合 这一题给定的集合范围是 [ 1, n ]，而本题给定的集合范围为 [ 1, 9 ]。

与 77. 组合 相同的是，都要从给定的集合范围内挑选 k 个数的组合，但本题增加了一个约束条件：组合内的元素之和要等于 n 。

我们可以用一个变量来保存 path 内的元素之和，将它记为 sum ，path 增删元素时，对应的需要修改 sum 的值。（不懂 path 是什么的同学，可以看一下完整题解：216. 组合总和III）

当 path 的元素个数等于 k 时，说明我们已经找到了一个组合，接着我要们判断 sum 是否等于 n，如果相等，说明这个组合符合题目要求。

代码如下：

  1. void backtracking(int startIndex) {
  2.     // 终止条件
  3.     if (path.size() == k) {
  4.         // 如果 sum == n
  5.         if (sum == n) {
  6.             // 加入到结果集中
  7.             result.add(new ArrayList<>(path));
  8.         }
  9.         return;
  10.     }

此外，由于本题是求和，所以可以先对题目给出的集合排序，方便剪枝，具体细节可以看一下完整题解：216. 组合总和III

17. 电话号码的字母组合

题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
例如：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

从示例上来说，输入”23”，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。

如果输入”233” 呢，那么就三层 for 循环，如果 “2333” 呢，就四层 for 循环…….

我们需要一层循环遍历题目给出的 digits 中的每个数字，一层循环遍历每个数字对应的字符。

显然，这个问题还是可以用回溯法来解决嵌套层数的问题。因为回溯法是用递归来做层叠嵌套的（可以理解是开 k 层 for 循环），每一次的递归中嵌套一个 for 循环，那么递归就可以用于解决多层嵌套循环的问题了

本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而 77.组合、216.组合总和III 都是求同一个集合中的组合。

理解本题后，要解决如下三个问题：

  1. 两个字母就两个 for 循环，三个字符我就三个 for 循环，以此类推，然后发现代码根本写不出来

解决：用回溯法来解决 n 个 for 循环的问题，将回溯抽象为树形结构，而叶子节点就是我们要收集的结果。

  1. 数字和字母如何映射

解决：可以使用 map 或者 二维数组，例如：String[] letterMap，来做映射。

  1. 输入1 * #按键等等异常情况

解决：代码中最好考虑输入1 #按键等这些异常情况，但本题没有异常情况的数据（digits[i] 是范围 [‘2’, ‘9’] 的一个数字），但*如果是现场面试中，一定要考虑到。

39. 组合总和

题目：给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

示例：

输入: candidates = [2,5,3], target = 8
输出: [[2,2,2,2],[2,3,3],[5,3]]

虽然题目规定元素可以无限制重复被选取，提示中说明 1 <= candidates[i] <= 200 所以不用特别考虑元素为 0 的情况。

本题和 77.组合、216.组合总和III 的区别是：本题给定的集合区间，允许重复选择同一个元素，且没有数量限制。

如果将本题搜索的过程抽象成树形结构，那么因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过 target ，就将其终止。
而在 77.组合、216.组合总和III 中都可以知道要递归 K 层，因为要取 k 个元素的组合。

因为本题要求解集不能包含重复的组合，所以仍然需要 startIndex 来控制 for 循环的起始位置。

题目规定 candidates 中的数字可以无限制重复被选取，因此在递归调用 backtracking 时，i 就不用 +1 了，表示可以重复选择当前数字：

// 关键点:不用i+1了，表示可以重复读取当前的数
backtracking(i);

本题的约束条件是求和，因此我们可以对题目给出的集合先做排序。那么下一层的 sum（就是本层的 sum + candidates[i] ）已经大于 target ，就可以结束本轮 for 循环的遍历，这样就不会进入下一层无效递归了。（完整题解：39. 组合总和）

本题的剪枝优化，这个优化如果是初学者的话并不容易想到。在求和问题中，排序之后加剪枝是常见的套路。

40. 组合总和II

题目：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
]

回想一下，是不是感觉和 216. 组合总和III、39. 组合总和 这两道题很像？有什么区别呢？

本题没有明确告诉你，给定的集合中，元素是否会重复！这也是本题的难点。

如果先把所有组合求出来，再用 set 或者 map 去重，这么做很容易超时。应该尽可能在搜索的过程中就去掉重复组合。

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

具体去重的思路可以看本题的详细题解：40. 组合总和II 。

组合问题总结

这几题做下来大概你也能感觉到了，去重是容易混淆的难点，这里组合问题的总结主要围绕去重来讲。

组合会重复的原因是什么？因为题目给定的集合中有元素重复。

因此，对于组合问题去重，我认为分两种情况：

  • 题目允许对集合元素进行排序：我推荐使用 90. 子集II 中补充的方法。不使用 used 数组来去重，因为递归的时候下一个 startIndex 是 i+1 而不是 0 。因此去重可以这么写：

    if (i > startIndex && nums[i] == nums[i - 1] ) {
      continue;
}

  • 题目不允许对集合元素进行排序：可以使用 491. 递增子序列 这道题的去重思路。在每一层的 for 循环之前定义一个 used 数组 / map / set 等数据结构作为哈希表，用来记录本层元素是否重复使用，这样新的一层递归， used 都会重新定义（清空），所以 used 只负责本层。

如果是排列问题的话，startIndex 每次要从 0 开始遍历，为了跳过已入栈的元素，就需要 used 数组来记录当前 树枝/分支 上的元素使用情况了，跟上述的“记录本层元素使用情况”就不一样了。

关于排列问题的去重，后面会仔细讲。

2、分割问题

131. 分割回文串

题目：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

切割问题与组合问题非常相似。

例如对于字符串abcdef：

  • 组合问题：选取一个 a 之后，在bcdef 中再去选取第二个，选取 b 之后在 cdef 中在选取第三个…..，直到无可选元素为止。
  • 切割问题：切割一个 a 之后，在 bcdef 中再去切割第二段，切割 b 之后在 cdef 中在切割第三段…..，直到无可选元素为止。

感受出来了不？

不过本题有个约束条件：切割后，每个子串都得是回文串。

所以切割问题，同样也可以抽象为一颗树形结构。如下图：
image.png
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

最后，再实现一个用于判断回文子串的函数即可。

93. 复原IP地址

题目：给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

示例：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

做这道题目之前，最好先把 131.分割回文串 这个做了。

这道题目相信大家刚看的时候，应该会一脸茫然。其实只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的 131.分割回文串 就十分类似了。

startIndex 一定是需要的，因为不能重复分割，用它来记录下一层递归分割的起始位置。

本题我们还需要一个变量 pointCount，记录添加逗点的数量。并且在添加 . 号时，直接拼在字符串 s 后，所以不需要 path 变量。

递归调用时，下一层递归的 startIndex 要从 i+2 开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量 pointCount 要 +1。
回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointCount 也要 -1。

最后实现一个 isValid 验证函数用于验证子串是否合法，主要考虑到如下三点：

  • 段位以 0 为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于 255 了不合法

分割问题总结

切割问题同样也可以抽象为一颗树形结构，不难发现，其回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

在处理分割问题的时候，可以递归参数需要传入startIndex ，表示下一轮递归遍历的起始位置，这个 startIndex 就是切割线。

字符串分割的另一个特征就是对分割的子串一般带有约束性要求，比如 131. 分割回文串、93. 复原IP地址。

3、子集问题

下面我们回顾一下子集的问题。

78. 子集

题目：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

示例：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

子集问题和组合问题、分割问题就不太一样了。

如果把子集问题、组合问题、分割问题搜索的过程抽象成一颗树形结构的话：

  • 组合问题和分割问题都是收集树的叶子节点
  • 子集问题是找树的所有节点。

其实子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和 子集 {2,1} 是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for 就要从 startIndex 开始，而不是从 0 开始。

求排列问题的时候，for 就要从 0 开始，因为集合是有序的，{1, 2} 和 {2, 1} 是两个集合

那么，把求子集问题的搜索过程抽象成一颗树形结构，如下图：
image.png

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

当 startIndex 大于数组的长度时，就没有元素可取了，此时剩余集合为空，便是终止条件了，即叶子节点。

其实可以不需要加终止条件，因为 startIndex >= nums.length，本层 for 循环本来也结束了。

显然求取子集问题，不需要任何剪枝。因为求子集就是要遍历整棵树。

90. 子集II

题目：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

示例：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

做本题之前一定要先做 78. 子集 。

这道题目和 78. 子集 区别就是集合里有重复元素了，需要对求取的子集去重。

组合问题去重，只要对同一树层上的元素去重就可以了。套路在 40. 组合总和II 中已经详细讲解过了，本题也是一样的。

491. 递增子序列

题目：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

提示：

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

示例：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

这个递增子序列比较像是取有序的子集，而且本题也要求不能有相同的递增子序列。

实际上这道题就是加了约束条件的子集问题，并且与 90. 子集II 很像，又是子集又是去重的，要注意差别所在，要不就掉坑里了。

在 90. 子集II 中我们是通过排序，再加一个标记数组 used 对同一树层的重复元素去重，以此达到对子集去重的目的。

而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑。

本题要求去重，但却无法对元素进行排序，这是本题的难点。

本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。

为了有鲜明的对比，我用 [4, 7, 6, 7] 这个数组来举例，抽象为树形结构如图：
image.png

本题其实类似求子集问题，也是要遍历树形结构找每一个节点，所以和 78. 子集 一样，可以不加终止条件，startIndex每次都会加1，并不会无限递归。但本题收集结果有所不同，题目要求递增子序列大小至少为 2 ，这点需要注意。

我们可以通过在每一层的 for 循环之前定义一个 used 作为哈希（根据不同题型，可以自由选择 set / map / 数组），用来记录本层元素是否重复使用。新的一层 used 都会重新定义（清空），所以 used 只负责本层。

这样就无需对集合先排序，也能去重了。

这道题是子集问题的重点，好好体会。

子集问题总结

要意识到子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和 子集 {2,1} 是一样的。

如果把子集问题、组合问题、分割问题搜索的过程抽象成一颗树形结构的话：

  • 组合问题和分割问题都是收集树的叶子节点
  • 子集问题是找树的所有节点。

其他的就和组合没什么区别了，建议你跳到组合问题总结那边再看复习一遍。

4、排列问题

下面我们回顾一下排列的问题。

46. 全排列

题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

示例：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

相信这个排列问题就算是让你用 for 循环暴力把结果搜索出来，这个暴力也不是很好写。

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要在使用一次 1 ，所以处理排列问题就不用使用 startIndex 了，因为每次都要从 0 开始。

如果将本题搜索的过程抽象成树形结构，可以看出叶子节点，就是收割结果的地方。
image.png

那么什么时候，算是到达叶子节点呢？

当收集元素的数组 path 的大小达到和 nums 数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

那么去重呢？组合问题去重是可以使用 startIndex 来控制的，因为组合不关心顺序，没有先选哪个后选哪个的问题。但排列不一样，因此不能用 startIndex 来控制去重。

从图上可以看出，排列问题选择元素时，要先排除掉当前同一树枝上的已选元素。也就是说，我们只要知道当前分支上已选择的元素就可以防止重复选择了。

那么有两种做法：

  1. 结合上面的树形结构图，我们定义一个 used 来标记当前分支上已经选择的元素，让 used 与 path 同步维护，path 增删元素， used 都要对应添加或撤销该元素的标记，这样就可以根据 used 来去重，防止重复选择了。
  2. 直接判断 path 中是否含有该元素即可，因为 path 记录的便是当前分支上的所有元素。

这里需要注意，第 1 种方法虽然也使用了 used ，但与 491. 递增子序列 这道题的去重思路是有区别的：

  • 491. 递增子序列 这道题的去重是在每一层的 for 循环之前定义一个 used 数组 / map / set 等数据结构作为哈希表，用来记录本层元素是否重复使用，这样新的一层递归， used 都会重新定义（清空），所以 used 只负责本层。
  • 本题使用的 used 需要记录的不是本层元素的使用情况，而是当前分支的元素使用情况，需要将 used 定义为类变量，而不是像 491. 递增子序列 这道题那样在每一层的 for 循环之前定义。

本题是一道标准的排列模板题，完整题解链接：46. 全排列

47. 全排列 II

题目：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

示例：

输入：nums = [1,1,2]
输出：
[
    [1,1,2],
     [1,2,1],
     [2,1,1]
]

这道题和 46. 全排列 的区别是：这道题给定的集合元素是包含重复数字的。
相同之处是：都是求解不重复的全排列。

这里又涉及到去重了。 在 40. 组合总和II 我们详细讲解了组合问题如何去重，本题也可以按照同样的套路，使用 used 去重。

我在组合问题总结时，推荐不使用 used 来解决组合去重。现在看来，这种方法反而更像是适用于排列去重，并且可以套在组合去重上而已。

以示例中的 [1,1,2] 为例 （为了方便举例，已经排序）将本题搜索的过程抽象成树形结构，可以看出抽象为一棵树，去重过程如图：
image.png

与 46. 全排列 不同的是，本题因为集合内元素重复，所以在树的同一层上是可能出现重复元素的。

显然，我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个排列里的元素，不用去重。

因此我们可以参考 40. 组合总和II 去重的思路

  1. 先对题目给定的集合做排序，这样我们才方便通过相邻的节点来判断是否重复使用了
  2. 将 used 定义为类变量，这样 used 就是在记录同一树枝上的所有元素使用情况了
  3. 在 backtracking 函数内部的 for 循环中根据 used[i - 1] 状态就可以判断 candidates[i-1] 是否在同一树层被使用过了，当 candidates[i] == candidates[i - 1] 时：
    1. 若 used[i - 1] == true，说明同一树支使用过 candidates[i - 1]
    2. 若 used[i - 1] == false，说明同一树层使用过 candidates[i - 1]
  4. 所以只要在 for 循环中判断，当 candidates[i] == candidates[i - 1] 时，若 used[i - 1] == false ，即代表当前元素在当前同一树层中出现过。

提起树层去重，你可能会想起 491. 递增子序列 去重的思路

  1. 在每一层的 for 循环之前定义一个 used 数组 / map / set 等数据结构作为哈希表，用来记录同一树层的元素是否重复使用
  2. 这样新的一层递归， used 都会重新定义（清空），所以 used 只负责本层

虽然这样可以解决树层去重，但还有一个问题需要解决：如何记录同一分支上的所有元素？因为同一树枝上的元素是允许重复的。该元素在题目给定的集合中重复出现几次，在同一树枝上也要允许其出现几次。

这样的问题虽然可以用 map 解决，但显然效率没有参考 40. 组合总和II 去重的思路的去重方案高。且本题是求解排列的，允许对集合做排序，因此我们可以使用相邻的节点来判断在树层上是否重复使用了。

本题没有参考 491. 递增子序列 树层去重方案是有原因的。

排列问题总结

排列问题的难点依然是搞清楚如何去重。

回溯问题都可以抽象为树形结构，排列问题也不例外。

那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

回看一下题目，元素在同一个排列内是可以重复的，怎么重复都没事，但两个排列不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个排列里的元素，不用去重。

与组合的去重不同的是，排列在要求对同一树层去重的同时，还要记录同一分支上的所有元素使用情况，保证任意元素只能使用一次，这也是排列问题去重的难点。

该如何解决呢？

可以参考 40. 组合总和II 去重的思路

  1. 先对题目给定的集合做排序，这样我们才方便通过相邻的节点来判断是否重复使用了
  2. 将 used 定义为类变量，这样 used 就是在记录同一树枝上的所有元素使用情况了
  3. 在 backtracking 函数内部的 for 循环中根据 used[i - 1] 状态就可以判断 candidates[i-1] 是否在同一树层被使用过了，当 candidates[i] == candidates[i - 1] 时：
    1. 若 used[i - 1] == true，说明同一树支使用过 candidates[i - 1]
    2. 若 used[i - 1] == false，说明同一树层使用过 candidates[i - 1]
  4. 所以只要在 for 循环中判断，当 candidates[i] == candidates[i - 1] 时，若 used[i - 1] == false ，即代表当前元素在当前同一树层中出现过。

这样 used 在充当记录当前分支元素使用情况的同时，还能通过相邻的节点来判断当前树层是否重复使用了，即对树层去重。

灵魂一问：组合与排列的去重有什么区别？

现在能回答上来了吗？

5、路线问题

…

6、棋盘问题

51. N 皇后

题目：n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

提示：

  • 1 <= n <= 9
  • 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

示例 1：
image.png

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

都知道 N 皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列、行程问题之后，遇到这种二维矩阵还会有点不知所措。

如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。

棋盘的宽度就是 for 循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

详细题解可以看 51. N 皇后 。

37. 解数独

题目：编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 ‘.’
  • 题目数据 保证 输入数独仅有一个解

示例：
image.png

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
image.png

51.N皇后 每一行每一列只放一个皇后，因此只需要一层 for 循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置即可。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比 N 皇后更宽更深。

本题需要一个 for 循环遍历棋盘的行，一个 for 循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放 9 个数字的可能性。其实就是在

最后还需要一个判断坐标数字是否合法的函数即可。

最后你需要注意的是，解数独问题需要求的答案只有一个，因此 backtracking 函数的返回值可以用 boolean 代替 void。

棋盘问题总结

与组合问题、分割问题、子集问题、排列问题不同的是：棋盘问题需要一个 for 循环遍历棋盘的行，一个 for 循环遍历棋盘的列，一行一列确定下来之后，递归遍历棋盘上的所有空格，最后根据题目给的约束条件实现一个 valid 函数，去验证这个空格上的数据是否符合要求。

关于回溯的问题

1、排列和组合的去重有什么区别？

回溯问题都可以抽象为树形结构，排列问题和组合问题也不例外。

那么“元素使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

组合去重：元素在同一组合内是允许重复的，任意两个组合不能重复。
组合问题去重的是同一树层上的“使用过”，且因为使用了 startIndex 控制元素遍历起始位置，可以保证一个元素只使用一次，因此无需记录同一分支上的所有元素使用情况。如下图（40. 组合总和II）
image.png

排列去重：元素在同一个排列内也是可以重复的，任意两个排列不能重复。
排列问题除了要去重的是同一树层上“使用过”，还要记录同一分支上的所有元素使用情况，这也是排列问题去重的难点。

因此，我认为排列问题去重和组合问题去重的区别就在于是否要记录同一分支上的所有元素使用情况。

最后补充一下，其实对于排列问题去重，对同一树层去重或对同一分支去重，实际上都是可以的，只不过对同一树层去重效率会更高。我在 47. 全排列 II 的拓展中，也详细解释了为什么。