22. Generate Parentheses

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: String、Dynamic Programming、Backtracking

一、題目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

  • Input: n = 3
  • Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

  • Input: n = 1
  • Output: ["()"]

Constraints:

  • 1 <= n <= 8

二、分析

  • DFS 演算法是在遍歷「節點」，而回溯法是在遍歷「樹枝」。站在一個節點上，需思考三個問題：
    1. 路徑(PATH)：已做出的選擇。
    2. 選項(OPTION)：當前可以做的選擇。
    3. 終止條件(TERMINATE)：到達決策樹的底層，無法再做其它選擇。
    • 以下為回溯法的框架：
    vector<PATH> res;
void backtrack(PATH, OPTION) {
    if (TERMINATE) {
        res.push_back(PATH);
        return;
    }
    for (CHOICE : OPTION) {
        DO OPTION;
        backtrack(PATH, OPTION);
        CANCEL OPTION;
    }
}
    • 本題的終止條件是當 path 的長度為 2n 的時候。
    • 而選項是增加左括號 ( 與增加右括號 )。
    • 加上兩個子節點的條件便完成，
      • 左節點需滿足 left < n。
      • 右節點需滿足 right < n && right < left。
  • DP 動態規劃則需觀察轉移方程式。
    • dp[0] base case： ``
    • dp[1] 很容易得到：()
    • dp[2] 也不難：()()、(()) 接下來觀察 dp[3]，可以分解為下面三個：
      1. ( + dp[0] + ) + dp[2]：()()()、()(())
      2. ( + dp[1] + ) + dp[1]：(())()
      3. ( + dp[2] + ) + dp[0]：(()())、((())) 換句話說，轉移方程式可以寫成：dp[i] = "(" + dp[j] + ")" + dp[i-j-1]

三、解題

1. Backtrack

vector<string> generateParenthesis(int n) {
    string path;
    vector<string> res;
    backtrack(n, 0, 0, res, path);
    return res;
}
void backtrack(int n, int left, int right, vector<string>& res, string& path) {
    // terminate
    if (path.length() == 2*n) {
        res.push_back(path);
        return;
    }

    // select
    if (left < n) {
        path.push_back('(');
        backtrack(n, left+1, right, res, path);
        path.pop_back();
    }
    if (right < n && right < left) {
        path.push_back(')');
        backtrack(n, left, right+1, res, path);
        path.pop_back();
    }
}

2. Dynamic Programming

  • Time complexity: \(O(n^4)\)
  • Space complexity: \(O(n)\)
vector<string> generateParenthesis(int n) {
    vector<vector<string>> dp(n+1);
    dp[0] = {""}; 
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            vector<string> left = dp[j];
            vector<string> right = dp[i-j-1];
            for(int k=0;k<left.size();k++){
                for(int l=0;l<right.size();l++){
                    dp[i].push_back("(" + left[k] + ")" + right[l]);
                }
            }
        }
    }
    return dp[n];
}

回目錄 Catalog