題目描述:給定正整數 n,產生所有包含 n 對括號的合法組合字串。
解題思路:使用**回溯法(Backtracking)**遞迴地建構字串。維護兩個計數器:open(已使用的左括號數)和 close(已使用的右括號數)。在每一步有兩個選擇:
open < n,可以加入 (close < open,可以加入 )(右括號不能多於左括號)當字串長度達到 2n 時,表示找到一個合法組合。此策略在建構過程中即保證合法性,不會產生無效字串再篩選,效率遠高於暴力枚舉。
時間複雜度:O(4^n / sqrt(n)) — 合法括號組合的數量是第 n 個卡特蘭數(Catalan number),漸近為 4^n / (n^(3/2) * sqrt(π))。
空間複雜度:O(n) — 遞迴呼叫堆疊深度最大為 2n(字串長度),不計儲存結果的空間。
1. Define backtrack(current, open, close, n):
a. If len(current) == 2*n: add current to result; return
b. If open < n: append '(', recurse with open+1, pop '('
c. If close < open: append ')', recurse with close+1, pop ')'
2. Call backtrack("", 0, 0, n)
3. Return result動態規劃 O(C_n):dp[i] 為所有 i 對括號的合法組合集合。dp[i] 可由 dp[j] 和 dp[i-1-j] 組合而來(對應「左括號內有 j 對,右側有 i-1-j 對」)。時間複雜度相同,但需要更多記憶體儲存所有中間結果。
暴力枚舉 + 驗證 O(n * 2^(2n)):枚舉所有 2n 個字元的字串,再逐一驗證合法性。時間複雜度遠差,不實用。
()、[]、{}),如何修改此解法?