LeetCode 解題筆記：22. Generate Parentheses

作者：王一哲
日期：2026年10月2日


LeetCode 題目連結：22. Generate Parentheses

解題想法

中等難度題。題目給一個正整數 $n (1 \leq n \leq 8)$，要産生 $n$ 對 () 所有合法的排列方式，也就是括號必須成對。這題要用 dfs 窮舉所有可能的排列方式，並且在目前已經選到的排列方式不合法時提早剪枝，或是確定加上一個左或右括號還是合法排列方式時才遞迴。由於 $n$ 最大值只有 $8$，即使寫法效率差一點也能過關。

Python 程式碼

Runtime: 3 ms, beats 30.52%. Memory: 19.53 MB, beats 10.33%.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans, path = [], []  # 答案，選到的字元

        # dfs 窮舉
        def dfs(balance):
            # 剪枝，如果 ( 比 ) 多，不合法
            if balance < 0: return

            # 剪枝，如果 ( 數量大於 n，不合法
            if balance > n: return
            
            # 遞迴出口，path 長度等於 2*n
            if len(path) == 2*n:
                # 合法的括號對，path 接成字串加入 ans
                if balance == 0:
                    ans.append("".join(path))
                return
            
            # 試著加入 ( 或 )，遞迴
            path.append('(')
            dfs(balance + 1)
            path.pop()
            path.append(')')
            dfs(balance - 1)
            path.pop()
        
        # 呼叫 dfs，從 balance = 0 開始測試
        dfs(0)
        return ans

Runtime: 3 ms, beats 30.52%. Memory: 19.48 MB, beats 36.93%.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans, path = [], []  # 答案，選到的字元

        # dfs 窮舉，代入左、右括號數量 left, right
        def dfs(left, right):
            # 遞迴出口，path 長度等於 2*n，path 一定合法
            if len(path) == 2*n:
                ans.append("".join(path))
                return
            
            # 如果 left < n，可以加入 (
            if left < n:
                path.append('(')
                dfs(left + 1, right)
                path.pop()  # 回溯
            
            # 如果 right < left，可以加入 )
            if right < left:
                path.append(')')
                dfs(left, right + 1)
                path.pop()  # 回溯
        
        # 呼叫 dfs，從 (0, 0) 開始測試
        dfs(0, 0)
        return ans

C++ 程式碼

Runtime: 5 ms, beats 15.65%. Memory: 13.45 MB, beats 69.78%.

class Solution {
public:
    vector<string> ans;
    string path;

    void dfs(int balance, int n) {
        // 剪枝，如果 ( 比 ) 多，不合法
        if (balance < 0) return;

        // 剪枝，如果 ( 數量大於 n，不合法
        if (balance > n) return;
        
        // 遞迴出口，path 長度等於 2*n
        if ((int)path.size() == 2*n) {
            // 合法的括號對，path 接成字串加入 ans
            if (balance == 0) {
                ans.push_back(path);
            }
            return;
        }
        
        // 試著加入 ( 或 )，遞迴
        path += "(";
        dfs(balance + 1, n);
        path.pop_back();  // 回溯
        path += ")";
        dfs(balance - 1, n);
        path.pop_back();  // 回溯
    }

    vector<string> generateParenthesis(int n) {
        ans.clear();
        path.clear();
        dfs(0, n);
        return ans;
    }
};

Runtime: 3 ms, beats 67.20%. Memory: 13.28 MB, beats 74.61%.

class Solution {
public:
    vector<string> ans;
    string path;

    void dfs(int left, int right, int n) {
        // 遞迴出口，path 長度等於 2*n
        if ((int)path.size() == 2*n) {
            ans.push_back(path);
            return;
        }
        
        // 如果 left < n，可以加入 (
        if (left < n) {
            path += "(";
            dfs(left + 1, right, n);
            path.pop_back();  // 回溯
        }

        // 如果 right < left，可以加入 )
        if (right < left) {
            path += ")";
            dfs(left, right + 1, n);
            path.pop_back();  // 回溯
        }
    }

    vector<string> generateParenthesis(int n) {
        ans.clear();
        path.clear();
        dfs(0, 0, n);
        return ans;
    }
};