LeetCode - 22. 括号生成_Pseudocode

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

原题：22. 括号生成

题目大意：给定一个 n，生成 n 对括号的有效排列，例如给定的 n 是 3，则有效的排列是：["((()))","(()())","(())()","()(())","()()()"]。

通常这样的排列组合题目可以使用递归和深度优先遍历来完成，先把递归的架子写出来：

``` java void dfs() { // 递归的终止条件，也就是在什么情况下不在进行递归调用

// 处理当前层的逻辑

// 进行下一层的递归调用

// 如果需要的话，再恢复递归调用钱的状态

} ```

然后，我们需要两个变量：

一个列表来保存结果集
一个 StringBuffer 用来拼接每一个可能结果

``` java class Solution { List result = new ArrayList<>(); StringBuffer sb = new StringBuffer(); public List generateParenthesis(int n) { dfs(0, 0, n); return result; }

private void dfs() {
    // 递归的终止条件，也就是在什么情况下不在进行递归调用

    // 处理当前层的逻辑

    // 进行下一层的递归调用

    // 如果需要的话，再恢复递归调用钱的状态
}

} ```

接下来，处理 dfs 方法中的逻辑就可以了。这里的关键是如何生成有效的括号排列，需要满足以下条件：

如果已经排列的左括号的数量小于 n，则可以追加左括号，也就是，只要左括号没用完，任何时候都可以追加
如果已经排列的右括号比做扩好少，就可以追加右括号，也就是成对的一组括号，左括号要比右括号线出现。

满足以上两个条件就可以了。

最终代码：

``` java class Solution { List result = new ArrayList<>(); StringBuffer sb = new StringBuffer(); public List generateParenthesis(int n) { dfs(0, 0, n); return result; }

private void dfs(int l, int r, int n) {
    // 递归的终止条件，也就是在什么情况下不在进行递归调用
    // 当结果的长度是括号数量的两倍时，就结束递归
    if (sb.length() == n * 2) {
        result.add(sb.toString());
        return;
    }

    // 追加半括号时，满足上述的任意条件，都可以追加对应的半括号
    // 完成递归调用之后，要把之前追加的半括号删除

    if (l < n) {
        // 处理当前层的逻辑
        sb.append('(');
        // 进行下一层的递归调用
        dfs(l + 1, r, n);
        // 如果需要的话，再恢复递归调用钱的状态
        sb.deleteCharAt(sb.length() - 1);
    }
    if (r < l) {
        // 处理当前层的逻辑
        sb.append(')');
        // 进行下一层的递归调用
        dfs(l, r + 1, n);
        // 如果需要的话，再恢复递归调用钱的状态
        sb.deleteCharAt(sb.length() - 1);
    }
}

} ```