题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

算法思路

类似于生成全排列问题，之前做过总结。 DFS求全排列总结 对dfs过程比较生疏的可以阅读一下。

dfs + 回溯解题框架

dfs算法的过程其实就是一棵递归树，所有的dfs算法的步骤大概有以下几步：

• 找到中止条件，即递归树从根节点走到叶子节点时的返回条件，此时一般情况下已经遍历完了从根节点到叶子结点的一条路径，往往就是我们需要存下来的一种合法方案
• 如果还没有走到底，那么我们需要对当前层的所有可能选择方案进行枚举，加入路径中，然后走向下一层
• 在枚举过程中，有些情况下需要对不可能走到底的情况进行预判，如果已经知道这条路不可能到达我们想去的地方，那我们干嘛还要一条路走到黑呢，这就是我们常说的剪枝的过程
• 当完成往下层的递归后，我们需要将当前层的选择状态进行清零，它下去之前是什么样子，我们现在就要让它恢复原状，也叫恢复现场。该过程就是回溯，目的是回到最初选择路口的起点，好再试试其他的路。

这里也是一个关于左右括号的排列问题，但是它对左右括号的顺序和个数有一定的要求，限制条件有：

1. 左括号和右括号的个数均为n
2. 任意一个子序列，右括号的数目必须小于等于左括号的数目

所以我们dfs的过程，就是选择当前是选择加最括号还是右括号的过程，选择时必须遵循上述的限制条件。

C ++代码

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        if (n == 0) return res;
        dfs(0, 0, n, "");
        return res;
    }

    void dfs(int l, int r, int n, string s) //左括号个数，右括号个数，要求个数，当前序列
    {
        if ( l == n && r == n) //左右括号达到数目
        {
            res.push_back(s);
            return;
        }

        if (l < n) dfs(l + 1, r, n, s + '('); //左括号还不够
        if (r < l) dfs(l, r + 1, n, s + ')'); //右括号必须小于等于左括号的个数
    }
};