算法训练营day23 | {77.组合, 216.组合总和III, 17.电话号码的字母组合}

第七章回溯算法part01，把问题抽象成树形结构，用回溯三部曲分析。

0. 理论基础

0.1 什么是回溯

• 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。之前在二叉树系列题目中，提到过回溯是递归的副产品，有递归就会有回溯。

0.2 回溯法的效率

• 虽然回溯法很难，但并不是什么高效的算法，回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。如果想让回溯法高效一些，可以加一些剪枝的操作，但也改变不了回溯法就是穷举的本质。
• 一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

0.3 回溯法解决的问题

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

0.4 如何理解回溯法

• 回溯法解决的问题都可以抽象为树形结构，用图形去理解它，所有的回溯法的问题都可以抽象为树形结构。
• 递归就要有终止条件，所有必然是一棵高度有限的树（N叉树）。

0.5 回溯法模板

回溯法的函数起名字一般为backtracking，列出回溯三部曲：

1. 回溯函数的返回值以及参数

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

  void backtracking(参数)

2. 回溯函数的终止条件
   • 既然是树形结构，和二叉树递归一样，遍历树形结构一定要有终止条件。什么时候到达了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

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

3. 回溯搜索的遍历过程（单层搜索的逻辑）

• 回溯法一般是在集合中递归搜索，集合的大小构成了树的高度，递归的深度构成树的深度。
  
• for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
• backtracking这里自己调用自己，实现递归。
• 从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

因此，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

77. 组合

• 题目链接：77. 组合
• 文档讲解：代码随想录–77. 组合
• 视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！
• 状态：单层搜索的逻辑中，往往是for循环+递归的，这个跟以前不一样啊。

1.1 解题分析

• 本题直接的解法，是用for循环解决，比如当n=4，k=2时，可以用两个for循环，输出和示例中一样的结果。

  int n = 4;
  for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
          cout << i << " " << j << endl;
      }
  }

  但是当n=20，k=10时，就是10层for循环，虽然思路是这样的，但是写10层嵌套for循环也太不优雅了。怎么办呢？用回溯搜索法。

• 看了题解之后，可以发现回溯法和上面的嵌套for循环本质上是一样的，同样是穷举暴力搜索，区别是，暴力写法需要嵌套10层for循环，而回溯法用递归来解决嵌套层数的问题。递归来做层叠嵌套，每一次的递归中嵌套一个for循环，相当于开k层for循环。

• 回溯法解决的问题都可以抽象为抽象树形结构，将组合问题抽象为如下树形结构，直观看到回溯搜索和for循环一样都是暴力穷举：
  

• 分析回溯算法三部曲：

  1. 参数和返回值是什么？ 返回值为void，参数包括给定的整数n、k，当前遍历存储的path列表，存储所有结果的result列表。还需要一个参数int型变量startIndex，这个参数用于记录本层递归当中，集合从哪里开始遍历。
  2. 确定递归的终止条件。 如果path的大小已经达到k，说明我们找到了一个子集大小为k的组合，找到了一个可行解，终止本层递归。并把结果保存道result列表里。
  3. 确定单层搜索的过程。 for循环是用来横向遍历的，遍历集合中的元素，用startIndex来控制起始遍历点，对于剪枝，也要通过for循环这里控制，对没有可能找到解的子节点直接剪掉；递归用来纵向遍历，和回溯配合使用。

• 回溯搜索法–无剪枝

  ▶

  77. 组合

  class Solution {
      public List<List<Integer>> combine(int n, int k) {
          List<List<Integer>> result = new ArrayList<>();
          List<Integer> path = new ArrayList<>();
          backtracking(n, k, 1, path, result);
          return result;
      }
  
      public void backtracking(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> result) {
          if (path.size() == k) {
              result.add(new ArrayList<>(path));
              return;
          }
          for (int i = startIndex; i <= n; i++) {
              path.add(i);
              backtracking(n, k, i + 1, path, result);
              path.remove(path.size() - 1);
          }
      }
  }

关于path和result数组设置为形参还是全局变量：path不是每一层递归各自独立的副本，它是一条被不断修改、不断回退的同一条路径，两种写法都用的是同一个path对象、用的是同一个result容器，回溯逻辑不受影响，所以是等价的。不过path代表当前递归层正在处理什么，放在参数中是很适合的。

• 回溯搜索法–剪枝优化

如果for循环选择的起始位置之后的元素个数，已经不足以构成k个数了，那么就没有必要继续搜索，应该剪枝。

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

▶

77. 组合

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtracking(n, k, 1, path, result);
        return result;
    }

    public void backtracking(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtracking(n, k, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

216. 组合总和III

• 题目链接：216.组合总和III
• 文档讲解：代码随想录–216.组合总和III
• 视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III
• 状态：这题画图之后还是简单的。

2.1 解题分析

• 分析回溯算法三部曲：

  1. 参数和返回值是什么？ 返回值为void，参数包括n、k，一个startIndex，用于记录当前递归层，集合从哪里开始遍历，同时把path列表和result列表定义为全局变量，提高可读性，sum也要作为递归的参数传入！
  2. 确定递归的终止条件。 如果path的大小已经达到了k，终止本层递归。如果path中元素的sum正好等于n，那么找到了一个可行解，在终止前把结果保存到result中。
  3. 确定单层搜索的过程。 for循环用于横向遍历，从startIndex开始，遍历当前节点的孩子（1-9）；递归用于纵向遍历，和回溯配合使用。

• 第一遍写时犯的错误

  • 这题的核心状态是什么？我们在递归中，其实只关心三件事：

  • 状态	含义
    path.size()	已经选了几个数
    sum	当前和是多少
    startIndex	下一次能从哪个数开始选
    所以sum必须是递归状态的一部分，而不是我需要的时候再从path里算出来。

  • 第二点，终止条件写错了，不管sum是不是n，达到个数了都必须要return，否则会继续往下选。

• 关于剪枝

  1. 和已经超了，没必要继续搜索；
  2. 数量不可能凑够了。

▶

216. 组合总和III

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {

        backtracking(k, n, 1, 0);
        return result;
    }

    public void backtracking(int k, int n, int startIndex, int sum) {
        if (sum > n) return; // 剪枝 和已经超了
        if (path.size() == k) {
            if (sum == n) result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            backtracking(k, n, i + 1, sum + i);
            path.remove(path.size() - 1);
        }
    }
}

2.2 题解总结

• 关于回溯三部曲，看了代码随想录之后，有了新的观点。
  • 首先，确定递归函数参数，这里sum这个参数也可以省略，每次targetSum减去选取的元素数值，做减法，如果targetSum < 0了，那同样说明和已经超了。并且强调，回溯法中的递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。
  • 和已经超了这个剪枝，也可以放在 调用递归 之前，只不过和我想的不一样，还需要做回溯操作，代码如下：

    for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
        sum += i; // 处理
        path.push_back(i); // 处理
        if (sum > targetSum) { // 剪枝操作
            sum -= i; // 剪枝之前先把回溯做了
            path.pop_back(); // 剪枝之前先把回溯做了
            return;
        }
        backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
        sum -= i; // 回溯
        path.pop_back(); // 回溯
    }

17. 电话号码的字母组合

• 题目链接：17.电话号码的字母组合
• 文档讲解：代码随想录–17.电话号码的字母组合
• 视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合
• 状态：暴力的for循环好想出来，但是怎么抽象成一个树形结构呢？？每个节点是 不同的集合

3.1 解题分析

• 将问题抽象为树形结构：
  

• 分析回溯算法三部曲：

  1. 参数和返回值是什么？ 定义全局变量，一个stringbuilder s来记录当前结果，一个列表result记录所有可行解；形参包括给定的digits，一个int型变量index，是用来遍历digits的，记录遍历到第几个数字了。
  2. 确定递归的终止条件。 当每个数字都被遍历过了，就收集结果，结束本层递归。
  3. 确定单层搜索的过程。 首先取到index指向的数字，并且找到对应的字符集，返回for循环来处理这个字符集，注意递归和回溯配合。

▶

17. 电话号码的字母组合

class Solution {
    StringBuilder s = new StringBuilder();
    List<String> result = new ArrayList<>();

    String[] digitMap = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        backtracking(digits, 0);
        return result;
    }

    public void backtracking(String digits, int index) {
        if (index == digits.length()) {
            result.add(s.toString());
            return;
        }
        int digit = digits.charAt(index) - '0';
        for (int i = 0; i < digitMap[digit].length(); i++) {
            s.append(digitMap[digit].charAt(i));
            backtracking(digits, index + 1);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

• 和前两题不同，本题是多个集合求组合，所以抽象出的树形结构是上图所示的，相应的，回溯函数的形参中index所表示的含义也不一样。

4. 今日收获

• 又开始新的知识点了，回溯算法实际上就是一种穷举的暴力搜索算法，解决此类问题要会把问题抽象成一个树形结构，在此基础上去分析参数、终止条件、以及单层搜索的逻辑。
• 学习时长：4小时