runtime 0 ms, beats 100% of cpp submissions
O((4^n)/sqrt(n)) solution with explanation

tags: recursion

Generate Parentheses

📖 description

給定一個數字 n ，生成一組由 n 個括號組成的合法字串

ex.
    n = 3
    output: ["((()))","(()())","(())()","()(())","()()()"]

🧠 solution

本題的重點在於生成一個 合法的 字串，且生成的過程必須導向一個合法的結果。

其實只要在每個狀態時都滿足左括號比右括號多 (或等於)，字串組合到最後一定是合法的。

考慮長度是 5 的狀態，以下幾個是合法的
ex.
    (())(, ()()(, ((())

因為如果右括號比較多，表示一定有個配對被提早結束了

考慮長度是 5 的狀態，以下幾個是不合法的
ex.
    )())(, ())(), (()))

⏳ time complexity

總共的遞迴次數為正確答案共有幾個 (計算有點難懂 pass)
總時間複雜度 O((4^n)/sqrt(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> ans;
    void gen(string& now,int l,int r){
        if(l==0 && r==0){               // 當組合完畢
            ans.emplace_back(now);
            return;
        }
        if(l>0){                        // 如果左括號還有剩
            string left = now + "(";    
            gen(left,l-1,r);
        }
        if(r>l){                        // 如果左括號比右括號多
            string right = now + ")";
            gen(right,l,r-1);
        }
    }
    vector<string> generateParenthesis(int n) {
        ans.clear();
        string tmp;
        gen(tmp,n,n);                   // 組合總共需要各 n 個左括號與右括號
        return ans;
    }
};