Leetcode Hot 100 | 回溯法

最近在刷力扣，总结一些算法专题的思想。好记性不如烂笔头，不然全都忘记了。

思想

回溯法，我认为是有一套模板的。

class Solution {
private:
    vector<T> result;
    T path;
    // other attributes

public:
    void dfs(some input, current progress) {
        if (progress == end) {
            result.push_back(path);
            return;
        }

        for (auto opt : all_valid_options) {
            edit input;
            path.push_back(opt);
            dfs(input, new progress);
            path.pop_back();
            undo input;
        }
    }

    vector<T> entryFunc(input, other_args) {
        Initialize attributes;
        for (every possible location) {
            dfs(input, start);
        }

        return result;
    }
};

做出一些说明：

回溯法的思想是穷举，所以，用人的思路来想，穷举需要什么？核心是结果和当前进度，分别对应 result 和 path；
在进行 dfs 时，需要知道要操作的对象(input)、当前的进度(progress)。如果到了回溯尽头，则将回溯的结果(path)加入 result 中；
在进行 dfs 时，需要以当前状态为开始，遍历所有可能的下一步，这可能通过循环、手写的几个选择或者条件判断来决定哪些“下一步”是合法的；
在进行 dfs 时，递归之前，需要对公共状态进行修改，加入 path；从递归中返回后，需要撤回对公共状态的修改，并从 path 中弹出；
在入口函数进入 dfs 之前，可能需要进行一些初始化工作，包括但不限于赋值属性。

例题

前文讲了思想，下面来看看 Hot 100 中的回溯法题目。

17. Letter Combinations of a Phone Number

电话拨号盘的数字对应一些字母。这道题的要求是，给了一串数字，要求枚举这些数字可能组成的所有字母组合。

class Solution {
private:
    vector<string> result;
    string path;
    vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    void dfs(string& digits, int start) {
        if (start == digits.size()) {
            result.push_back(path);
            return;
        }

        for (char c : map[digits[start] - '0']) {
            path += c;
            dfs(digits, start + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        dfs(digits, 0);
        return result;
    }
};

这道题是回溯法的经典了，在 private 属性中存在 result 和 path 这两个属性，此外还有一个 map 成员用来方便获知每个号码对应的可选字符。

在 dfs 部分，判断回溯完毕的条件是当前位置的索引和号码的长度一致，这意味着已经对所有数字完成了选择。而递归前，将当前字母加入 path，递归后弹出。

在入口函数部分，没有复杂的其他初始化操作，只需要从 0 号下标开始。

这题需要注意的地方是，下标要 - 0，因为输入的是字符串，每个字符减 0 才是我们想要的数组下标。

22. Generate Parentheses

这题的要求是生成 n 对合法的括号，可以嵌套、可以并列等等。

class Solution {
private:
    vector<string> result;
    string path;
public:
    void dfs(int left, int right) {
        if (left == 0 && right == 0) {
            result.push_back(path);
        }

        if (left > 0) {
            path += '(';
            dfs(left - 1, right);
            path.pop_back();
        }

        if (right > left) {
            path += ')';
            dfs(left, right - 1);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n, n);
        return result;
    }
};

本题也算比较规整。值得注意的是对于状态的定义，这里 left 和 right 分别表示有多少个左括号 / 右括号可用。

判断终止条件时，如果二者都为 0，说明回溯完毕，记录结果。

判断可选的状态转移时，如果左括号还可以选择，那就加入左括号；如果右括号比左括号剩的多（意味着有左括号可以来匹配），则可以加入右括号。

39. Combination Sum

这题的要求是，给了一个集合和一个目标，集合的每个数可以用无数次，问有哪些（去重）组合求和后等于目标。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
public:
    void dfs(vector<int>& candidates, int at, int remain) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }

        for (int i = at; i < candidates.size(); i++) {
            if (candidates[i] > remain) {
                break;
            }

            path.push_back(candidates[i]);
            dfs(candidates, i, remain - candidates[i]);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return result;
    }
};

这题稍微有些变化了。首先，在进行 dfs 之前，对数组进行排序，目的是可以在 dfs 中根据数列递增的特点，终止递归。

下面关注 dfs 函数。它需要维护两个状态：当前考虑到哪个位置了，以及距离目标还差多少。如果达到了目标，记录，回溯完毕。而在一个状态中，可选的是从它到它之后的所有数字，不考虑之前的，否则会有重复(e.g [2, 2, 3] and [3, 2, 2])。而如果当前数字超过了剩余，则不考虑后续，因为数列递增，后续的肯定比当前值大。

其实这里也可以选择不排序，并把 break 改为 continue。因为根据状态考虑的思想，如果不排序，从当前位置及之后的都是合法选择。权衡一下吧，排序有额外的复杂度，但是可以剪枝；不排序则反过来。

46. Permutations

这道题的要求是生成数组的全排列。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> selected;
public:
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (!selected[i]) {
                selected[i] = true;
                path.push_back(nums[i]);
                dfs(nums);
                selected[i] = false;
                path.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        selected.assign(nums.size(), false);
        dfs(nums);
        return result;
    }
};

这题有些不同点在于状态与初始化部分。注意到，dfs 中并没有接收状态参数，而是只有输入。状态参数是 selected，它是一个向量，而不是下标、剩余值等标量，所以并不能像前面的几个题解一样作为参数传入。Instead，这里把状态用数据成员的方式来维护，调用 dfs 前修改状态，调用完毕恢复。

终止条件是 path 的长度等于 nums 的大小。这是个很有意思的观点：path 的长度有时候也可以作为一个状态，不过有时候可能用其他的状态 (left, right, start) 等更有语义信息。

51. N-Queens

N 皇后问题，不必多说。

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path;
    vector<bool> diag1, diag2, col;
    int _n;
public:
    void dfs(int row) {
        if (row == _n) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < _n; i++) {
            if (diag1[i + row] && diag2[_n + row - i - 1] && col[i]) {
                diag1[i + row] = diag2[_n + row - i - 1] = col[i] = false;
                path[row][i] = 'Q';
                dfs(row + 1);
                path[row][i] = '.';
                diag1[i + row] = diag2[_n + row - i - 1] = col[i] = true;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        diag1.assign(2 * n - 1, true);
        diag2.assign(2 * n - 1, true);
        col.assign(n, true);
        path.assign(n, string(n, '.'));
        _n = n;
        dfs(0);
        return result;
    }
};

这题是道 Hard，必然有它的原因。我认为，难度有以下几点：

状态维护复杂，逐行遍历，需要维护三个状态数据的信息；
棋盘的状态表示有些困难，如果是第一次，可能反应不出来怎么用字符串的方式维护棋盘。

一点点分析，其实发现，这道题也是个模板。

result 和 path 两个老朋友还在，没什么可说的。而 dfs 的状态维护和上一题又有不同：这里既涉及标量状态，又涉及向量状态。标量的 row 直接传入，3 个规则向量需要作为数据成员来维护。

3 个规则向量有必要展开讲讲，根据 N 皇后的规则：皇后不能在同行、同列、同主、副对角线见面。因为我们是逐行遍历的，所以需要用状态表示后三条规则。一个棋盘中，有 2 * n - 1 条对角线和 n 个列，这就是初始化中数字的含义。

而关于行列坐标与规则向量之间的对应关系，我觉得不必强行记忆，而是可以动态地推导：当前位置如果 row + 1，对于对角线的下标是什么贡献？如果是 col + 1 呢？这样就能够推导出关系来了。

关于棋盘状态的表示，应该要记住 assign 这个方法，在上一题我们也见到了。记忆起来不是很难，和初始化的写法类似。

最后，关于终止条件的判断，注意到，这里也并不能通过输入或者状态判断是否完成了回溯（之前的 .size()、left == 0 && right == 0 都不好使了），因此提取出了变量 _n。

78. Subsets

这题的要求是找出一个集合的幂集。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
public:
    void dfs(vector<int>& nums, int idx) {
        if (idx == nums.size()) {
            result.push_back(path);
            return;
        }

        dfs(nums, idx + 1);

        path.push_back(nums[idx]);
        dfs(nums, idx + 1);
        path.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return result;
    }
};

没什么好多说的，是一道经典的回溯模板题，一切都非常基础。值得一提的是，关于下一步的选择，这里没有用循环，而是类似于 22 题，手写了当前的抉择：选或不选该元素加入集合。

79. Word Search

这题的要求是在二维字符数组中，找出是否存在一条路径上的字母组合成目标单词。

class Solution {
private:
    vector<vector<char>>* pBoard;
    int _m, _n;
    string _word;
public:
    bool dfs(int x, int y, int idx) {
        if (idx == _word.size()) return true;
        
        if (x < 0 || x >= _m || y < 0 || y >= _n || (*pBoard)[x][y] != _word[idx]) {
            return false;
        }

        char tmp = (*pBoard)[x][y];
        (*pBoard)[x][y] = '#';

        bool res = dfs(x - 1, y, idx + 1) || dfs(x + 1, y, idx + 1) || dfs(x, y - 1, idx + 1) || dfs(x, y + 1, idx + 1);
        
        (*pBoard)[x][y] = tmp;
        return res;
    }

    bool exist(vector<vector<char>>& board, string word) {
        _m = board.size();
        _n = board[0].size();
        _word = word;
        pBoard = &board;
        
        for (int i = 0; i < _m; i++) {
            for (int j = 0; j < _n; j++) {
                if (dfs(i, j, 0)) return true;
            }
        }

        return false;
    }
};

这题有点意思，我第二次做居然还没有 AC。看上去和我们之前讲的套路有些差别，path 也没有，result 也没有。说实话，我觉得这题更适合放在 Graph 那部分。不过既然它放到回溯法里，我们也可以分析一下。

首先，还是状态，这里，状态体现在 board 中，是否有对某个位置访问过，如果有，则替换为 # 防止重复访问。另一个状态体现在当前遍历的位置是什么。我们之前考虑的遍历都是一维的，一个下标记录就完成了，但这里不同，图上的遍历不是线性的，判断终止也没有那么容易。

所以，我们要自己写出来，站在当前位置（坐标），可以前进的方向是？上下左右！只要不出棋盘的边界。何时终止？当前字符和 word 字符不同时。这里的 idx 记录的是与 word 的哪个字母比对，如果出现了不同，则说明，这次回溯到头了，不满足情况。

最后，对于终止条件，定义了 _m 和 _n。对于向量状态，维护了一个 pBoard 指针。

131. Palindrome Partitioning

这题的要求是找到一个字符串的切割，使得切割后产生的字串都是回文串。

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path;
    vector<vector<bool>> isPalin;
    string _s;
public:
    void dfs(int start) {
        if (start == _s.size()) {
            result.push_back(path);
            return;
        }

        for (int end = start; end < _s.size(); end++) {
            if (isPalin[start][end]) {
                path.push_back(_s.substr(start, end - start + 1));
                dfs(end + 1);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        int n = s.size();

        isPalin.assign(n, vector<bool>(n, false));

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 2 || isPalin[i + 1][j - 1])) {
                    isPalin[i][j] = true;
                }
            }
        }
        
        _s = s;
        dfs(0);

        return result;
    }
};

这题是回溯法的最后一题，大致还是遵守之前我们说的模板，有的地方有不同，需要点出。

判断是否是回文串，需要初始化一个数组，这样比较方便，用到了动态规划的内容。

具体的决策逻辑，还是老样子：当前的起始坐标下，哪些决策合法？那些切割后是回文串的合法。据此做出选择。选择后，位置变成了当前切割串的下一个位置。