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);
    }
}

} ```