22-括号生成 回溯法及其模板

参考负雪明烛大佬对此的讲解。喜欢的可以多关注这个大佬，对leetcode题解做的很充分详细了。（链接：https://leetcode-cn.com/problems/generate-parentheses/solution/ru-men-ji-bie-de-hui-su-fa-xue-hui-tao-lu-miao-don/）

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。

一般回溯的问题有三种：

Find a path to success 有没有解
Find all paths to success 求所有解
求所有解的个数
求所有解的具体信息
Find the best path to success 求最优解
回溯法是一个剪枝了的二叉树。我们要得到的结果是可以 good leaf，如果不满足 good leaf 就继续向下搜索，搜索的时候需要满足一定的条件。

那么我们在什么情况下添加左括号呢？很明显，最多能添加 n 个左括号，在递归调用的时候，在能传递到最底层的共用字符串中先添加 ”(“ ，然后 left-1，递归调用就可以。

那什么时候添加右括号呢？当左括号个数大于右括号的个数时添加右括号。

总之，向下搜索要满足两个条件：

插入数量不超过n
可以插入 ） 的前提是 ( 的数量大于 ）
回溯法的代码套路是使用两个变量： res 和 path，res 表示最终的结果，path 保存已经走过的路径。如果搜到一个状态满足题目要求，就把 path 放到 res 中。

代码后面的判断条件都是 if，而不是 elif，因为是满足两个条件的任意一个就可以继续向下搜索，而不是同时只能满足其中的一个。

使用C++，基本结构和上面一样，不过这里 lc 和 rc 分别表示左括号的个数和右括号的个数。vector的push_back()方法调用的时候实际上是使用的值传递，也就是会进行赋值到vector里。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        int lc = 0, rc = 0;
        dfs(res, "", n, lc, rc);
        return res;
    }
    void dfs(vector<string>& res, string path, int n, int lc, int rc) {
        if (rc > lc || lc > n || rc > n) return;
        if (lc == rc && lc == n) {
            res.push_back(path);
            return;
        }
        dfs(res, path + ‘(‘, n, lc + 1, rc);
        dfs(res, path + ‘)‘, n, lc, rc + 1);
    }
};

View Code

22-括号生成 回溯法及其模板

原文：https://www.cnblogs.com/nxnslc-blog/p/12670819.html