53. Generate Parentheses

読了目安約2分

Greedy / Backtracking / LeetCode 22 (Medium) — 正しい括弧列を n 組ぶんすべて生成する

この章の目次

問題

LeetCode 22. Generate Parentheses（Medium / カテゴリ: Greedy / Backtracking）

整数 n が与えられます。 ( と ) を n 個ずつ使ってできる、対応の取れた括弧列をすべて返す問題です。 n は最大 8 で、n = 3 の答えは ((())), (()()), (())(), ()(()), ()()() の 5 個です。

返す順序は自由です。このページのテストコードは、結果をソートしてから期待値と比較します。

考え方

ヒント 1

1 文字ずつ追加するバックトラッキングです。すべての並びを作ってから検査するのではなく、正しい括弧列に伸ばせる追加だけを許します。

ヒント 2

追加済みの ( の数 open と ) の数 close を持ちます。 ( は open < n のとき、) は close < open のときだけ追加できます。この 2 条件を守って長さ 2n まで伸ばした文字列は、必ず対応が取れています。

Swift 実装のポイント

文字列も配列と同じく append と removeLast() で末尾を操作できます。var current = "" を 1 本使い回します。
完成の判定は open == n && close == n です。条件を守って伸ばしているので、完成形を検査し直す必要はありません。
答えの個数は n = 8 でも 1430 個なので、すべて生成しても間に合います。

模範解答

Swift
class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result: [String] = []
        var current = ""
        func backtrack(_ open: Int, _ close: Int) {
            if open == n && close == n {
                result.append(current)
                return
            }
            if open < n {
                current.append("(")
                backtrack(open + 1, close)
                current.removeLast()
            }
            if close < open {
                current.append(")")
                backtrack(open, close + 1)
                current.removeLast()
            }
        }
        backtrack(0, 0)
        return result
    }
}

計算量: O(生成される括弧列の個数 × n)。