[LeetCode] 22. Generate Parentheses

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

• Time complexity: \(O(2^{2n})\)，Wiki - Catalan number
• Space complexity: \(O(n)\)

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