[数据结构与算法]回溯算法1：回溯初探

告别数据结构和变型题之后，我们开始征服三个基础算法：回溯、贪心和动态规划。很多书籍教程都是将动态规划放在最前面的。但是说实话动态规划实在有些难度的，一旦学不清楚，就会感觉回溯和贪心也很难，所以我们就反过来。

经常有人问算法有没有捷径，比如告诉我这个方法适用什么范围，怎么解决问题的套路，最好给个代码的模板。其实是有的，但是只有在你做到一定程度之后才有作用，如果没怎么练过。那对不起，没有！什么方法都没用。

回溯就是非常典型的例子，回溯有非常清晰的适用场景，有非常清晰的典型问题，有非常明确的解题模板。如果会了一个，我们可以非常轻松地解决掉十几道典型的问题。

本模块很多内容参考了”代码随想录“、labuladong等等大量材料和书籍，有些截图啥的就直接拿来用了。?

本篇主要是为了感受一下回溯的基本特点和解决思路，而不针对具体问题展开，所以读者看的时候可能会有很多疑惑点，我们后面再详细展开。

0.前奏

? 不卖关子我们直接说四条结论，可能你现在看了还没啥感觉，先瞅一眼。后面我们会用大量的例子来检验和验证。

1.回溯是递归的拓展，而本身不是什么特别高效的方法。很多问题我们能采用暴力循环来解决，但是有些问题是暴力都解决不了，只能考虑回溯。

2.回溯有非常清晰的代码模板：

void backtracking(参数) 
{ if (终止条件) {
   存放结果;
   return; 
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) 
 {
    处理节点;
   backtracking(路径，选择列表); // 递归
   回溯，撤销处理结果
 } 
}

上面模板够简单吧，但是解决问题时很难想清楚，特别是”回溯，撤销处理结果“，这一条，为什么要撤销，怎么撤销。即使给你代码让你debug也很难搞清楚，所以我们需要下面这招：

3.回溯也是多叉树，但是回溯其实是在经过树枝时打印，而不是访问结点时。这样可以更方便解释上面代码里 为什么要撤销，如何撤销，以及剪枝等问题。如果现在不清楚没关系，我们后面详细展开。

4.回溯有自己能解决的典型问题，而不是什么问题都能用回溯，主要有以下几种：

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

现在我们分别来说明上面几条到底啥意思。

1.为什么会有回溯

我们前面说回溯主要是为了解决一些暴力都无法解决的问题。啥问题这里牛，竟然暴力都搞不定？

看一个例子：LeetCode77组合问题：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。例如

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

含义是：输入了4，那么 1~n，就是[1,2,3,4]。n为2，表示一共能有多少个只有2个元素的组合。
很明显有一下6个：
【1，2】，【1，3】，【1，4】
         【2，3】，【2.4】
                 【3，4】

明白了上面的意思，我们发现，那还不简单，两次循环就ok了：

 
int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
       System.out.print("i:"+i+" ;j: "+j);
} }

如果这里的n是3呢？也好办，三层for循环就行了：

 
int n = 10;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
          System.out.print(i+ "; "+j+" ; "+u);
} }

如果k是50，你怎么写？要写50层for循环吗？

另外，虽然题目的例子里k是2，但是k是可以变的，你该怎么设计循环的次数呢？

类似的问题还有子集划分，切割等问题，允许你大量使用if else，允许你大量使用for循环嵌套都写不出来。

所以，这种类型的问题，暴力法就无效了。

2.用多路树来分析组合问题

无法暴力解决的问题有很多，回溯只能解决其中一部分场景的问题。上面第二条我们说了回溯是有非常清晰的模板的。要想解理解通透，我们要先看第三条，通过树形结构来分析组合问题的本质是啥。

首先，我们画一下上面这个题的分析过程

?首先，我们从【1，2，3，4】中分别选取 1，2，3或者4来打头，并且不重复。取了1之后还可以有2，3，4三种选择，而最后取4时就没有选择了。所以就是上面从根节点到第二层的过程，我们可以看到这一层从左到右元素个数越来越少。

然后，在选了1之后，后面只能从【2，3，4】中选。如果选了2，则只能从【3，4】中选，而如果选了3，则只能选4了。这时候也就知道结果集合了。这就是上面第二层到第三层的过程。

上面这个图中，最后一层结果集是直接打印结果了，而不再是结点了，所以我们用[ ]表示。?

我们观察这个图，我们会发现几个有意思的特征：

1.所有的结果都是在一层的，而这个题里的k恰好就是树的深度2。也就是说我们用树枝表示选的是谁，然后到底之后时候打印出来就行了。

也就说如果我们在访问树枝的时候打印，是不是正是我们需要的结果？上面图里对应的就是：

• 先取1时：【1，2】【1，3】【1，4】
• 先取2时：【2，3】，【2，4】
• 先取3时：【3，4】

当然，你可以先从2，3，4任意开始，但是从小到大取符合我们一般的习惯。

2.第二层的节点数就是根节点的元素数。之后每个结点的分支数就是该结点的元素数。

第二层表示的就是你选了某个元素之后还剩下的元素，所以与根节点数是对应的。

因为每个结点的元素数可多可少，我们可以使用for循环来依次遍历，而不能简单使用二叉树的node.left和node.right来遍历了。

从图中可以看到，这个过程是递归的，每个节点的元素数就是该结点的子树。

3.从上面我们可以看到，for循环用来处理每个节点数的问题，而纵向其实就是递归的深度。这里k=2，所以我们递归的深度是2。

?4.撤回操作就是为了访问下一个节点时先去掉已经访问的元素

例如上面，我们得到第一个结果【1，2】时，下一个要得到的结果是【1，3】，所以我们必然要先将访问的2给去掉，也就是要撤销掉”取2“这个操作。这就是模板代码里为什么在递归后会有个”撤销“的操作。

这个地方如果仅仅靠调试或者文字很难说，而且越说越糊涂，看图就容易很多。下图红色向上就是撤销对应的”取*“操作的反向操作，因为图比较小，所以文字只标记了一个”撤销2“和”撤销4“，没有全部标记。

如果这个不理解，我们再看一个例子：实现[1, 2, 3]的全排列的例子，这个例子后面我们还会详细分析，这里感受一下”选择“和对应撤销的过程：

?3.解释回溯的解题模板

虽然我们开始以组合为例的?，而上面这个图，我们会发现仍然符合上面说的四个特征：

• 1.所有的结果都是在一层的，因为全排列每个结果里都是全部元素个数，所以树的深度就是3.
• 2.第二层的节点数就是根节点的元素数。之后每个结点的分支数就是该结点的元素数。
• 3.for循环用来处理每个节点数的问题，而纵向其实就是递归的深度。
• 4.撤回操作就是为了访问下一个节点时先去掉已经访问的元素

这就意味着这两类的题目可以用一个方式解决，所以就会形成相对固定的解题模板。我们来解释模板的含义。

我们在树的递归部分，也提到过递归有三步：

1. 确定方法名和返回值以及参数
2. 确定终止条件
3. 确定搜索的遍历过程

这在我们这里仍然适用。

（1）回溯函数模板返回值以及参数

在回溯算法中，起名随意，习惯是函数起名字为backtracking或者dfs等。

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

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

（2）回溯函数终止条件

既然是树形结构，历树形结构一定要有终止条件，所以回溯也有要终止条件。

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

if (终止条件) { 
  存放结果;
  return; 
}

（3）回溯的遍历过程：

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

而两个结合的代码极其简单，伪代码如下:?

 
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 
   处理节点;
   backtracking(路径，选择列表); // 递归
   回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。 backtracking这里自己调用自己，实现递归。

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

分析完过程，回溯算法模板框架就是下面这样子了:

void backtracking(参数) 
{ if (终止条件) {
   存放结果;
   return; 
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) 
 {
    处理节点;
   backtracking(路径，选择列表); // 递归
   回溯，撤销处理结果
 } 
}

怎么样，代码看上去很简单吧。

4.回溯解决问题举例

我们现在看几个例子，确定一下上面的模板是靠谱的。具体解释我们先不讲，后面文章逐个分析，这里感受一下。

我们说回溯只能解决特定场景的问题，主要是组合、排列、子集、切割、棋盘等相关问题，我们找几个案例拿过来看看。

（1）组合问题，LeetCode 77组合

给定两个整数?n?和?k，返回范围?[1, n]?中所有可能的?k?个数的组合。

解答：

public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是：path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历可能的搜索起点
        for (int i = begin; i <= n; i++) {
            // 向路径变量里添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }
}

（2）排列问题 LeetCode46.全排列?

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

例如，输入[1,2,3]，

输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

解答：

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(path);
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

}

（3）切割问题 LeetCode 131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

例如 输入: "aab"

输出: [["aa","b"],["a","a","b"] ]

public class Solution {

    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        Deque<String> stack = new ArrayDeque<>();
        char[] charArray = s.toCharArray();
        dfs(charArray, 0, len, stack, res);
        return res;
    }

    private void dfs(char[] charArray, int index, int len, Deque<String> path, List<List<String>> res) {
        if (index == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < len; i++) {
            if (!checkPalindrome(charArray, index, i)) {
                continue;
            }
            path.addLast(new String(charArray, index, i + 1 - index));
            dfs(charArray, i + 1, len, path, res);
            path.removeLast();
        }
    }
    private boolean checkPalindrome(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

观察上面的几个dfs案例，你是否发现代码非常类似？这就是我们说的回溯是有模板的。不过这个不是万能的，很多场景是需要做调整的。接下来我们就按照类型划分成几个小专题，分别研究。

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