22.括号生成

问题

思路Ⅰ ：动态规划

动态规划本质上就需要找到递推的规律。如果已经知道$i-1$对括号的有效括号式集，如何再添加一对括号得到$i$对括号的有效括号式集呢？

我们来看一个具体的例子。假设$i=2$，故有效括号式集为

$$(()),()()$$

现在考虑在何处添加新的括号对，可以使得得到的括号式仍然有效。为了方便思考，字符串最左侧的字符一定是”(“，于是我们将该字符和与之对应的右括号”)”视为新增的括号对。那么两个括号之间的部分，以及右括号右部的部分必然也是有效的，且它们加起来的括号对数即为$i-1$。为了方便后续的讨论，我们把前者包含的括号对数记作$p$，后者包含的括号对数记作$q$，而由$x$个括号对组成的有效括号式集合记作$S(x)$，个数记作$|S(x)|$。

状态转移

给定$i$个括号对，根据上面的分析，

$$S(i)=\{ '('+\mathrm{x}+')'+\mathrm{y}|\mathrm{x}\in S(p),\mathrm{y}\in S(q),p+q=i-1,\forall p \in [0,i-1] \}$$

由$p+q=i$，则有效括号式数量满足

$$|S(i)|=\sum_{p=0}^{i-1}\left(|S(p)|\times|S(i-1-p)|\right)$$

下面举一个具体的例子，仍然以上面的2对括号对为例，求解$S(3)$。注意，此时$S(0),S(1),S(2)$均已知。

$$\begin{aligned} S(0)&=\{\} \\ S(1)&=\{ () \} \\ S(2)&=\{ (()),()() \} \end{aligned}$$

下面求解$S(3)$。我们用$[]$来表示、强调新增的括号对。

$$\begin{aligned} & p=0,q=2,S(3)_{02} = \{ '('+\mathrm{x}+')'+\mathrm{y}|\mathrm{x}\in S(0),\mathrm{y}\in S(2) \} = \{ [](()),[]()() \} \\ &p=1,q=1,S(3)_{11} = \{ '('+\mathrm{x}+')'+\mathrm{y}|\mathrm{x}\in S(1),\mathrm{y}\in S(1) \} = \{ [()]() \} \\ & p=2,q=0,S(3)_{20} = \{ '('+\mathrm{x}+')'+\mathrm{y}|\mathrm{x}\in S(2),\mathrm{y}\in S(0) \} = \{ [(())], [()()] \} \end{aligned}$$

代码

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> dp[10];
        dp[0] = {""}, dp[1] = {"()"};
        int i, j;
        for(i=2; i<=n; i++) {
            for(j=0; j<i; j++) {
                // dp[j], dp[i-1-j]
                for(string x:dp[j]) {
                    for(string y:dp[i-1-j]) {
                        dp[i].push_back("("+x+")"+y);
                    }
                }
            }
        }
        return dp[n];
    }
};

思路Ⅱ：回溯

回溯算法和深度优先遍历很类似，都需要沿着某一个方向一直搜索。和深度优先遍历不同的是，回溯算法在搜索到某个不可能出现的状态时，就会立即终止当前搜索，即剪枝操作。

此题中，我们用已经拼接出的字符串done、还剩下的左括号数量left和右括号数量right来表示一个状态；凡是不合法的括号式均为不可能出现的状态（即当left>right），一旦搜索到该状态，便可以立即返回（剪枝）。但是我们可以调整一下搜索方式，便可以避免出现不合法状态：

• 当left=right且不为零时，此时只能选择左括号”(“，于是还剩余的左括号left数量减一、右括号数量right不变，DFS(done+"(", left-1, right)；
• 当left=0时，此时只能选择右括号”)”，于是还剩余的右括号right数量减一，左括号数量left不变，DFS(done+")", left, right-1)；
• 其余情况下，既可以选择左括号，也可以选择右括号
  • DFS(done+"(", left-1, right)
  • DFS(done+")", left, right-1)

边界条件

很显然，当left=right=0时，此时搜索到终止状态，将字符串done添加到集合之中即可。

代码

class Solution {
public:
    set<string> S;
    void DFS(string done, int left, int right) {
        if(left == 0 && right == 0) {
            S.insert(done);
            return;
        }
        if(left == 0)   DFS(done+")", left, right-1);
        else if(left == right) {
            DFS(done+"(", left-1, right);
        } else {
            DFS(done+"(", left-1, right);
            DFS(done+")", left, right-1);
        }
    }
    vector<string> generateParenthesis(int n) {
        DFS("", n, n);
        vector<string> vs;
        for(set<string>::iterator iter = S.begin(); iter != S.end(); iter++) {
            vs.push_back(*iter);
        }
        return vs;
    }
};

赏