摘要

• 回溯和递归是相辅相成的，用到回溯的地方一般都会有递归。递归是实现回溯的基本方法。
• 回溯法并不是很高效的算法，是一种暴力枚举法，通过枚举可能答案来解决问题。
• 回溯法提供了一种枚举各种可能性的方法，让一些难以用多层循环搜索答案的问题至少能用回溯法解决，如组合问题和切割问题。
• 所有的回溯法的问题都可以抽象为树形结构，即可能答案的构造是树形的。

回溯法基础

相关定义和概念

• 定义：回溯法也可以叫做回溯搜索法，是一种搜索的方式。
• 组合：可以理解为数学上的集合，并不强调元素的顺序和相对位置。
• 排列：可以理解为数学上的数列，强调元素的顺序。

回溯法的意义

• 回溯法的本质是穷举，穷举所有可能的答案，然后验证这些答案是否符合题目要求，选出合适的答案。
• 有一些问题只能用回溯法解决，目前并没有更高效的解法。

回溯法的理解

• 可能答案的枚举过程是树形的，可以通过画出答案的构造树来帮助思考。
• 回溯法的过程都可以抽象为N叉树。
• 回溯法解决的问题是在给定集合中递归查找子集，集合的大小决定了答案树的宽度（一个节点有几个孩子），递归的深度构成了答案树的深度。
• 递归用于向下找，循环用于在同一层中找

递归与循环

回溯法的模板

• 回溯法的递归函数一般没有返回值。
• 递归函数一般命名为backtracking。
• 回溯法的参数列表在一开始是不好确定的，会在分析问题的过程中逐渐完善。
• 先写递归的终止条件，在终止条件下收集结果。
• 然后写单层搜索的逻辑，一般情况下是for循环，用来处理当前集合里的每一个元素。用答案树来看，也可以对应处理当前节点的每一个子节点。
• for循环中一般做三件事：1. 处理当前节点；2. 调用递归函数；3. 撤销操作（回溯）

void backtracking(arg...) {
    if (/* 终止条件 */) {
        /* 收集结果 */
        return;
    }
    for (/* 每一个集合中的元素 */) {
        /* 1. 处理当前元素 */
        /* 2. 调用递归函数 */
        /* 3. 撤销处理（回溯） */
    }
    return;
}

还要继续理解和总结，先多写一些回溯法的题目。

LeetCode77 组合

77. 组合 - 力扣（Leetcode）

• 初见题目的想法：按照以上的回溯模板进行思考
  • 首先回溯法的递归函数不返回值
  • 递归函数命名为backtracking
  • 在分析问题的过程中确定参数列表
  • 先写递归的终止条件：当前组合cur的元素个数cur.size()等于k，则收集当前组合cur，然后直接返回。（这步确定需要传入的参数为结果集res，当前组合cur，元素个数k）
  • 再写单层搜索的逻辑：用for循环向cur中尝试加入元素（这步确定需要传入的参数为n，还有防止组合重复所需的元素的起始值j。
• 按照回溯法的模板进行思考，可以很容易的写出如下代码。我将当前组合命名为cur，和遍历二叉树时对节点的命名类似，提醒自己用树的形式去理解回溯法。cur对应的就是答案的构造树上的某个节点。

初见题目的题解代码如下

class Solution {
public:
    void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
        if (cur.size() == k) {
            res.push_back(cur);
            return;
        }
        for (int i = j; i <= n; i++) {
            cur.push_back(i);
            backtracking(res, n, k, cur, i + 1);
            cur.pop_back();
        }
        return;
    } 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(res, n, k, cur, 1);
        return res;
    }
};

以上代码的递归函数的参数列表里的cur没有传引用（vector<int> cur），多次拷贝vector，代码效率较差。

改为传引用vector<int>& cur，可见能显著提升效率。

class Solution {
public:
    void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int> cur, int j) {
        if (cur.size() == k) {
            res.push_back(cur);
            return;
        }
        for (int i = j; i <= n; i++) {
            cur.push_back(i);
            backtracking(res, n, k, cur, i + 1);
            cur.pop_back();
        }
        return;
    } 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(res, n, k, cur, 1);
        return res;
    }
};

• 组合问题较简单，在这里在复习一次回溯法的三步思考来总结今天的复习：

  1. 在分析问题的过程中确定递归函数需要的参数
  2. 确定递归的终止条件，在终止条件里收集结果
  3. 确定单层递归的处理逻辑

• 剪枝待第二天复习。