回溯算法的总结心得 第1篇

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：

树枝上去重（used[i - 1] == true）的树型结构如下：

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

这道题其实还是用了我们之前讲过的去重思路，但有意思的是，去重的代码中，这么写：

和这么写：

都是可以的，这也是很多同学做这道题目困惑的地方，知道used[i - 1] == false也行而used[i - 1] == true也行，但是就想不明白为啥。

所以我通过举[1,1,1]的例子，把这两个去重的逻辑分别抽象成树形结构，大家可以一目了然：为什么两种写法都可以以及哪一种效率更高！

这里可能大家又有疑惑，既然 used[i - 1] == false也行而used[i - 1] == true也行，那为什么还要写这个条件呢？

直接这样写 不就完事了？

其实并不行，一定要加上 used[i - 1] == false或者used[i - 1] == true，因为 used[i - 1] 要一直是 true 或者一直是false 才可以，而不是 一会是true 一会又是false。 所以这个条件要写上。

是不是豁然开朗了！！

13.重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

回溯算法的总结心得 第2篇

回溯法的性能如何呢，这⾥要和⼤家说清楚了，虽然回溯法很难，很不好理解，但是回溯法 并不是什么⾼效的算法 。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法⾼效⼀ 些，可以加⼀些剪枝的操作，但也改不了回溯法就是穷举的本质。 那么既然回溯法并不⾼效为什么还要⽤它呢？ 因为没得选，⼀些问题能暴⼒搜出来就不错了，撑死了再剪枝⼀下，还没有更⾼效的解法。 此时⼤家应该好奇了，都什么问题，只能暴⼒搜索

组合问题：N个数⾥⾯按⼀定规则找出k个数的集合 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式 ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式 棋盘问题：N皇后，解数独等等

例如：{1, 2} 和 {2, 1} 在组合上，就是⼀个集合，因为不强调顺序，⽽要是排列的话，{1, 2}和 {2, 1} 就是两个集合了。 记住组合⽆序，排列有序，就可以了。

题目：

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

⽰例: 输⼊: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 思路： 直接的解法当然是使⽤for循环，例如⽰例中k为2，很容易想到 ⽤两个for循环，这样就可以输出 和⽰例中⼀样的结果。 代码如下：

输⼊：n = 100, k = 3 那么就三层for循环，代码如下：

如果n为100，k为50呢，那就50层for循环，是不是开始窒息。 此时就会发现虽然想暴⼒搜索，但是⽤for循环嵌套连暴⼒都写不出来！

如果for循环选择的起始位置之后的元素个数 已经不⾜ 我们需要的元素个数了，那么就没有必要搜索了。

接下来看⼀下优化过程如下：

为什么有个+1呢，因为包括起始位置，我们要是⼀个左闭的集合。 举个例⼦，n = 4，k = 3， ⽬前已经选取的元素为0（为0），n - (k - 0) + 1 即 4 - (3 - 0) + 1 = 2。 从2开始搜索都是合理的，可以是组合[2, 3, 4]

回溯算法的总结心得 第3篇

在回溯算法:电话号码的字母组合中，开始用多个集合来求组合，还是熟悉的模板题目，但是有一些细节。例如这里for循环，可不像是在回溯算法:求组合问题! 和回溯算法:求组合总和!中从startIndex开始遍历的。 因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而回溯算法:求组合问题! 和回溯算法:求组合总和!都是是求同一个集合中的组合!

6、对于切割问题，切割回文串那道题目，难点在于以下方面：

7、对于求子集的问题，在子集问题一中，在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。在子集问题二中，需要对子集进行去重，逻辑与以前一样的，用一个used数组里进行标记。在递增子序列中，不能对原序列进行排序，也可以使用set针对同一父节点本层去重。

8、对于求排列的问题。排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

排列问题也要去重了，在回溯算法:排列问题(二)心中又一次强调了_树层去重_和”树枝去重”。

使用set去重的版本相对于used数组的版本效率都要低很多，主要是因为程序运行的时候对unordered_set频繁的insert,unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。 而使用used数组在时间复杂度上几乎没有额外负担!，使用set去重，不仅时间复杂度高了，空间复杂度也高了，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

回溯算法的总结心得 第4篇

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

首先来看一下皇后们的约束条件：

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

按照我总结的如下回溯模板，我们来依次分析：

我依然是定义全局变量二维数组result来记录最终结果。

参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

代码如下：

在如下树形结构中：

可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

代码如下：

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

代码如下：

按照如下标准去重：

代码如下：

在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？

因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。

那么按照这个模板不难写出如下C++代码：

可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。

本题是我们解决棋盘问题的第一道题目。

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

回溯算法的总结心得 第5篇

题目描述：

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

​思路：这个题目求的是全排列，所以这时候就不在需要传递起始位置了，因为求全排列，数字是可以重复使用的，不同的顺序是不同的结果。但是题目给定的数组有重复的元素，应该如何去重？其实这里的去重思路和上面的题目一样，也是在使用过这个数字，将要进行下一次 for 循环的时候，看一下下一个数字是不是一样，一样的话就跳过，同样也需要对原数组进行排序。这里对原数组进行排序也没有影响，因为求的是全排列，只要是这些数字，那么最后得到的全排列一定是一样的。好了，原数组中重复的数字问题解决了，也就是同层有重复数字的问题解决了。（树层去重）

但是还有一个问题需要考虑。我们在递归的时候，先把当前拿到的数字添加到结果中，然后进行下一次递归，但是因为求全排列，下一次递归的起始位置也是 0 。那么可以想一下在第一次递归的时候，拿到的是下标为 0  的数字，下一次递归又是这个数字，而我们希望不要在使用现在使用过的这个数字了，这时候怎么办？这一点其实是在 纵深 方向的去重，解决方法是定义一个数组用来标定已经使用过的数字，如果这个数字使用过了，那就进行标记，下次递归的时候只有没有标记的数字才可以使用，当递归返回的时候，再取消标记。其实就是回溯。这样就可以避免下次递归的时候又用到了之前的递归使用过的数字。对树层去重还有一个方法就是在每次递归的 for 循环之前定义一个数组，用于标定同层使用过的数字。注意是要每次递归的 for 循环之前都要重新定义，这样才能保证和每一层对应。（树枝去重）

所以总结一下，在求排列的时候，不仅要对树层去重，还要对同一树枝去重。

回溯算法的总结心得 第6篇

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

这又是子集，又是去重，是不是不由自主的想起了刚刚讲过的90.子集II (opens new window)。

就是因为太像了，更要注意差别所在，要不就掉坑里了！

在90.子集II (opens new window)中我们是通过排序，再加一个标记数组来达到去重的目的。

而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

回溯算法的总结心得 第7篇

在for (int i = startIndex; i < (); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在vector path中，path用来记录切割过的回文子串。

代码如下：

回溯算法的总结心得 第8篇

回溯用递归实现

递归是一种算法结构，回溯是一种算法思想；一个递归就是在函数中调用函数本身来解决问题；回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。

（1）首先要将问题转化，得出解空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。

（2）回溯法的实现步骤

通过读题完成下面三个步骤： 1)描述解的形式，定义一个解空间，它包含问题的所有解。 2)构造状态空间树。 3)构造约束函数（用于杀死节点）。 然后就要通过深度优先搜索思想完成回溯，完整过程如下： 1)设置初始化的方案（给变量赋初值，读入已知数据等）。 2)变换方式去试探，若全部试完则转(7)。 3)判断此法是否成功（通过约束函数），不成功则转(2)。 4)试探成功则前进一步再试探。 5)正确方案还未找到则转(2)。 6)已找到一种方案则记录并打印。 7)退回一步（回溯），若未退到头则转(2)。 8)已退到头则结束或打印无解

子集树和排列数是回溯法解题时常用的两个典型的解空间树

  所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。 如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。

在这想到了图的遍历的深度 优先搜索算法，对比一下

 深度优先搜索基本模型（其实和子集树模板一样）

待完善

所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。 如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。

待完善...

回溯算法的总结心得 第9篇

本题这涉及到两个关键问题：

相信这里不同的切割方式可以搞懵很多同学了。

这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。

一些同学可能想不清楚 回溯究竟是如何切割字符串呢？

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

感受出来了不？

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

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

全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）

本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

在回溯算法：求组合总和（二） (opens new window)中我们深入探讨了组合问题什么时候需要startIndex，什么时候不需要startIndex。

代码如下：

从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

回溯算法的总结心得 第10篇

选择过程树形结构如图所示：

可以看到图中，每个节点相对于 39.组合总和 (opens new window)我多加了used数组，这个used数组下面会重点介绍。

与39.组合总和 (opens new window)套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

这个集合去重的重任就是used来完成的。

代码如下：

与39.组合总和 (opens new window)相同，终止条件为 sum > target 和 sum == target。

代码如下：

sum > target 这个条件其实可以省略，因为在递归单层遍历的时候，会有剪枝的操作，下面会介绍到。

前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。

回溯算法的总结心得 第11篇

所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map> targets。

在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用_航班次数_这个字段的数字做相应的增减，来标记到达机场是否使用过了。

如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

回溯算法的总结心得 第12篇

咋整？

回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。

那么回溯法怎么暴力搜呢？

上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

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

此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。

一些同学本来对递归就懵，回溯法中递归还要嵌套for循环，可能就直接晕倒了！

如果脑洞模拟回溯搜索的过程，绝对可以让人窒息，所以需要抽象图形结构来进一步理解。

回溯算法的总结心得 第13篇

题目描述：

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路：这一题和前面的也是类似，这一次需要判断的是当前要放置棋子的位置是否合法。这里的棋子是皇后，这里普及一点点国际象棋小知识，皇后可以横着、竖着、斜着走。所以这里的合法判断就变成了判断当前位置的同行、同列、斜线是否存在皇后。这里一定要想清楚斜着走的话，行和列是怎么加减的，而且只需要向上判断，因为下面的棋盘还没处理。

首先进行棋盘的初始化，定义一个字符串数组，并全部初始化为题目要求的 点 。然后就开始进行递归，递归的是需要期盼的大小，棋盘和当前所在的行数。因为一行肯定只能放一个皇后，所以以行为单位进行for循环。在递归之前进行条件判断即可，是合法的位置就变为皇后，然后进行递归，如果不是合法的位置，那就进行下一轮循环，看看这一行的下一个位置合不合法。递归返回时记得要回溯，撤销之前的操作。

回溯算法的总结心得 第14篇

这道题目我使用回溯法，那么下面按照我总结的回溯模板来：

本题以输入：[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例，抽象为树形结构如下：

开始回溯三部曲讲解：

在讲解映射关系的时候，已经讲过了，使用unordered_map> targets; 来记录航班的映射关系，我定义为全局变量。

当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。

参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。

代码如下：

回溯算法的总结心得 第15篇

题目描述：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。

思路：这个题有一个特殊情况，那就是给定的数组中可能会有重复的元素，那么如果这个元素使用过了，后面再使用，那就会导致重复，但是我们又不能在一开始就删除掉重复的元素，否则就和给定的数组不一样了，结果肯定会不正确。所以我们只能在遍历的时候，一边遍历，一边进行去重的操作。

我的去重思路是这样：我们按照正常的递归回溯先操作，当递归返回的时候，将要进行下一次 FOR 循环 的时候，进行去重，如果下一个数字和这个使用过的数字是一样的，那就跳过，注意要是用while循环跳过，因为可能不止一个重复的。要想进行这样的操作必须首先对原数组进行排序，让相同的元素挨在一起。可是排序对原数组进行了修改，不会导致其它问题吗？这里我们找的是组合，和顺序没有关系，只要是这些数字，找到的就是这些组合，不会因为数组的顺序变化而导致组合的变化。

回溯算法的总结心得 第16篇

题目描述：

编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：

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

思路：看到这个题，回想起了之前上中学被数独游戏支配的恐惧，要是中学的时候会这个那多好，哈哈。这个题其实本质上还是换汤不换药，只不过递归时要进行的条件判断复杂了一些。

合法判断：同行、同列不能有重复数字，当前这个3*3 的格子内不能有重复数字。确定每一个小格子的起始位置想了挺久，后来发现是自己想复杂了，直接用 当前行 除以 3然后在 * 3，那就是起始位置，其实是利用了 整形除法的取整特性。本质上还是映射，就是把这个格子内的行列数都映射在这个格子的起始位置。

整体思路：利用两个 for 循环，遍历每一个位置，如果这个位置是数字，那就跳过，直接遍历下一个数字，如果是空格，那就对这个位置以及要放的数字进行合法判断，如果合法那就添加一个数字，如果不合法那就换一个数字再判断。如果这9个数字都用完了还不合法，那就无解。

这里的递归函数也有返回值，因为如果找到了合法的数独解，后面的就不用再遍历了。

回溯算法的总结心得 第17篇

一些写法，是把回溯的过程放在递归函数里了，例如如下代码，我可以写成这样：（注意注释中不一样的地方）

我不建议把回溯藏在递归的参数里这种写法，很不直观，我在二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)这篇文章中也深度分析了，回溯隐藏在了哪里。

所以大家可以按照版本一来写就可以了。

4.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

回溯算法的总结心得 第18篇

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

如果输入_233_呢，那么就三层for循环，如果_2333_呢，就四层for循环…

大家应该感觉出和77.组合 (opens new window)遇到的一样的问题，就是这for循环的层数如何写出来，此时又是回溯法登场的时候了。

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

可以使用map或者定义一个二维数组，例如：string letterMap[10]，来做映射，我这里定义一个二维数组，代码如下：

例如：输入：“23”，抽象为树形结构，如图所示：

图中可以看出遍历的深度，就是输入_23_的长度，而叶子节点就是我们要收集的结果，输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

回溯三部曲：

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。

再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。

这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。

代码如下：

例如输入用例_23_，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。

那么终止条件就是如果index 等于 输入的数字个数（）了（本来index就是用来遍历digits的）。

然后收集结果，结束本层递归。

代码如下：

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

然后for循环来处理这个字符集，代码如下：

注意：输入1 * #按键等等异常情况

代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。

回溯算法的总结心得 第19篇

题目描述：

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

例如：__ 和 __ 是 有效 IP 地址，但是 __、__ 和 __ 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路：这一题和上面一题的思路是一样的，只不过判断条件变了，然后多了一个插入 字符 的操作，并且是在原字符数组上进行操作。那么如何保证在原字符数字上操作，不会影响之后的遍历呢？答案就是回溯，当递归返回的时候，一切又会恢复原样。那终止条件是什么呢？根据题目，这些字符串一定会被分为 4 段， 也就是会添加 3 个点，我们可以用一个变量记录添加点的个数，如果这个添加点的个数等于3，那就终止。注意这里的变量是从0开始的，其实变量值等于2的时候就是插入3个点了，但是还会进行下次一递归，这时候就变成3了。

这里需要注意的点：在终止的时候，要对最后这一段子串进行合法判断，之后最后这一段也合法，这才是一个合理的划分。还有一个就是如果当前子串不合法，应该进行下一轮循环还是直接终止循环？答案是终止，因为这个题目和上一个题目不一样，这个题目如果当前子串不合法，那么不管在加多少字符，这个子串都不合法，所以直接终止。

回溯算法的总结心得 第20篇

题目描述：

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

​思路：这一题其实也是换汤不换药，但是这是一个求组合的题目，需要起始位置。不同点是加入的条件判断变成了只有比当前保存的结果数组最后一个数字大的才能加入这个结果数组，这样可以保证这个结果数组是升序。但是这个题目给定的数组是有重复的数字的，如果重复使用就会导致出现重复的序列。而且我们不能对这个原数组进行排序，然后按照之前总结过的当时去重，因为这个题目涉及到求子序列，改变原数组的顺序会改变子序列的顺序。那么我们只能用之前总结过的 树层 去重，在递归的 for 循环之前定义一个数组标记 当前树层 使用过的数字，后面在加入对是否使用过的判断条件即可。

小陷阱：在终止条件这里，每当结果数组大小大于2 的时候，就可以作为一个升序子序列了，但是这里一定不能直接返回，因为这个题目不是求最终的结果，而是相当于从根节点到叶子节点的每一个节点，只要符合条件都是一个升序子序列。那什么时候返回呢？起始位置超过数组最后一个位置的下标的时候就终止了。

回溯算法的总结心得 第21篇

题目描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

思路：用这个题来整理一下回溯问题的模板。题目的意思其实就是找组合，组合的元素个数是 K。组合无序，所以使用过的数字不能再使用，否则就重复了，所以越往后找其实需要遍历的越少。

递归函数参数：需要三个，分别是起始位置、要求的区间末尾数字、组合的大小。凡是组合类的问题，都需要一个起始位置作为参数，因为下一个递归需要从下一个位置开始。递归函数一般不需要返回值，但也有例外情况，有的情况加上一个返回值会提高搜索效率。

递归的逻辑：把当前的数字添加到结果中，然后在递归下一个数字。当递归返回时再弹出。

递归终止条件：只要当前的结果大小等于 K ，那这就是一个符合条件的结果，添加到结果集中。

回溯算法的总结心得 第22篇

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：这一题刚拿到肯定会有点懵，感觉好像知道要怎么做，但是具体的细节又不是很清楚，其实这是因为对水回溯还没有完全理解。拿到这样的题，首先第一步要建立映射关系，也就是把按键和字母对应起来。这道题目肯定是建立一个字符串数组了，因为每一个按键上有多个字母，到时候肯定要用到其中一个或几个，需要遍历。 

其次要考虑一下，如何对输入的数字进行拆分。例如输入了23，我们要分别对2和3对应的字符串进行梳理，如果输入234，那就分别对2，3和4对应的字符串进行处理。其实就是在 N 个数组中找所有的组合。之前做过在一个数组中找组合的，现在变成了 N 个。

关键点：用一个 index 表示现在用到的是输入数字的第几个数字。例如输入 23 ，那么 index = 0 表示现在使用的是2，index = 1表示现在使用的是3。而用这个 index 可以拿到这个数字对应的数组。拿到这个数组就可以进行递归遍历了。

回溯算法的总结心得 第23篇

这里给出Carl总结的回溯算法模板。

在讲二叉树的递归 (opens new window)中我们说了递归三部曲，这里我再给大家列出回溯三部曲。

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下：

既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

回溯算法的总结心得 第24篇

题目描述：

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

​思路：这个题目其实本质上就是一个回溯递归，只不过是在每次递归的时候要多进行一个条件判断，这个条件判断就是判断是不是回文串。判断回文串这里就不说了，双指针搞定。

整体思路就是利用递归，当前子串是回文串，那就递归，从下一个字符继续开始找是不是回文串。如果当前子串不是回文串，那就直接进行下一轮循环，看看再加进来一个字符是不是回文串。最后当开始位置大于等于数组的末尾的时候，是一个符合的结果，就把当前结果添加到结果集中。

这里有一个陷阱：要记住每次拿到的是一个子串，不是一个字符。例如第一次 for 循环拿到了 字符串 a ，第二次拿到的是 aa，第三次拿到的是 aab。那么当我们在一层进行遍历的时候，如果当前的子串不是回文串，我们是直接进行下一次循环还是直接中断循环呢？显然我们应该直接进行下一次循环，不进行递归(因为这个串不是回文串)，而直接进行下一次循环是因为 当前字符串不是回文串，但是如果再加进来一个字符，可能就是回文串了。比如 当前是 ab ，但是下一个字符是 a，加进来就变成了 aba ，这就是一个回文串了。如果是回文串那就进行下一次递归，递归返回时记得回溯。

回溯算法的总结心得 第25篇

这道题目相信大家刚看的时候，应该会一脸茫然。

其实只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串 (opens new window)就十分类似了。

切割问题可以抽象为树型结构，如图：

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

本题我们还需要一个变量pointNum，记录添加逗点的数量。

所以代码如下：

终止条件和131.分割回文串 (opens new window)情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。

然后验证一下第四段是否合法，如果合法就加入到结果集里

代码如下：

在for (int i = startIndex; i < (); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环，如图中剪掉的分支：

然后就是递归和回溯的过程：

递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。

回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。

代码如下：

最后就是在写一个判断段位是否是有效段位了。

主要考虑到如下三点：

代码如下：

可以写出如下回溯算法C++代码：

而且本题还需要操作字符串添加逗号作为分隔符，并验证区间的合法性。

在本文的树形结构图中，我已经把详细的分析思路都画了出来，相信大家看了之后一定会思路清晰不少

8.子集

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

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

回溯算法的总结心得 第26篇

来回顾一下排列/组合/子集问题的三种形式在代码上的区别。

由于子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。

形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，

backtrack 核心代码如下：

形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：