題目

給定 n 對括號，請寫一個函數產生所有可能的「合法括號組合」。

合法括號組合 指的是每個左括號 ( 都有對應的右括號 )，且順序正確。

範例

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

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

Constraints

1 <= n <= 8

解題思路

這題是經典的 DFS / 回溯算法 題目。
關鍵點：

每次決定加 ( 或 )，並遞迴嘗試。

左括號的數量不能超過 n。

右括號的數量不能超過左括號的數量。

這樣就能保證生成的每個括號組合都是合法的。

程式碼（Java）
import java.util.*;

class Solution {
public List generateParenthesis(int n) {
List result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}

private void backtrack(List<String> result, String current, int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }

    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }

    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

}

心得

這題看似簡單，但實際上是對「回溯法」的一個很好的練習。
重點在於：限制條件的判斷，確保不會生成非法組合。

回溯法的思路就是：

決定走哪一步（加 ( 或 )）

嘗試走下去

回退（Backtrack）到上一步繼續嘗試

這個問題很好用來訓練「DFS + 條件判斷」的邏輯。