22. Generate Parentheses

Medium

Description

給定 n 對括號，生成所有合法的括號組合。

Example:

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

Intuition#

核心思路：用回溯法逐步構建括號字串，只在合法時才加入開或閉括號——開括號數 < n 時可加開括號，閉括號數 < 開括號數時可加閉括號。

合法括號的條件：任何前綴中，開括號數 >= 閉括號數；最終開閉括號各 n 個
用 open 和 close 計數器追蹤已使用的括號數
回溯法在每步做出選擇（加開或加閉），不合法的路徑自然被剪枝

Approaches#

1: Brute Force + 驗證#

概念: 生成所有 2^(2n) 種長度 2n 的括號字串，逐一驗證是否合法
時間複雜度: O(2^(2n) * n) - 生成 2^(2n) 個候選，驗證各需 O(n)
空間複雜度: O(n) - 遞迴深度和字串長度

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()

        fun generate(current: String) {
            if (current.length == 2 * n) {
                if (isValid(current)) result.add(current)
                return
            }
            generate(current + "(")
            generate(current + ")")
        }

        generate("")
        return result
    }

    private fun isValid(s: String): Boolean {
        var count = 0
        for (c in s) {
            if (c == '(') count++ else count--
            if (count < 0) return false
        }
        return count == 0
    }
}

⭐2: Backtracking#

概念: 回溯法構建字串，用 open 和 close 計數控制：open < n 時可加 (，close < open 時可加 )
時間複雜度: O(4^n / sqrt(n)) - 第 n 個 Catalan 數
空間複雜度: O(n) - 遞迴深度

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()

        fun backtrack(current: StringBuilder, open: Int, close: Int) {
            if (current.length == 2 * n) {
                result.add(current.toString())
                return
            }

            if (open < n) {
                current.append('(')
                backtrack(current, open + 1, close)
                current.deleteCharAt(current.length - 1)
            }

            if (close < open) {
                current.append(')')
                backtrack(current, open, close + 1)
                current.deleteCharAt(current.length - 1)
            }
        }

        backtrack(StringBuilder(), 0, 0)
        return result
    }
}

補充：迭代法（Stack 模擬回溯）

用顯式堆疊模擬遞迴過程，每個狀態包含當前字串、開括號數、閉括號數。

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        val stack = ArrayDeque<Triple<String, Int, Int>>()
        stack.addLast(Triple("", 0, 0))

        while (stack.isNotEmpty()) {
            val (current, open, close) = stack.removeLast()

            if (current.length == 2 * n) {
                result.add(current)
                continue
            }

            if (close < open) {
                stack.addLast(Triple(current + ")", open, close + 1))
            }
            if (open < n) {
                stack.addLast(Triple(current + "(", open + 1, close))
            }
        }

        return result
    }
}

此題雖歸類在 Stack，但核心解法是 Backtracking。Stack 的連結在於：合法括號字串的驗證本質上就是堆疊操作（開括號入棧、閉括號出棧），以及可以用顯式 Stack 模擬遞迴。

🔑 Takeaways#

Pattern: 「列舉所有合法組合」用回溯法，關鍵在於找到剪枝條件
關鍵技巧: open < n 和 close < open 這兩個條件完美地在生成過程中維持合法性，無需事後驗證；用 StringBuilder 的 append/deleteCharAt 比字串串接更高效