バックトラックで正しく閉じた括弧の並びを全部作る

バックトラック問題 108

n 組の丸括弧で作れる、正しく閉じた並びを全部、辞書の順で作ります。開き括弧はあと何個置けるか、閉じ括弧は開いた数を越えないか、の 2 つの決まりで枝を切りながら 1 文字ずつ伸ばす、バックトラックの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数 n を受け取ります。開き括弧 ( を n 個と閉じ括弧 ) を n 個使ってできる、正しく閉じた並びを全部作り、文字列の並びで返す関数を書いてください。

正しく閉じた並びとは、左から読んでいくどの時点でも、閉じ括弧の数が開き括弧の数を越えず、最後に両方の数が同じになる並びです。"(())" や "()()" は正しく、")(" や "())(" は正しくありません
返す並びは、( を ) より前の文字と見た辞書の順にします。同じ並びを 2 回入れません
n は 1 以上 8 以下です

入力と出力の例

例 1

2 組では、入れ子の "(())" と、並べた "()()" の 2 つです。2 文字目が ( の方が先に来ます。

n = 2

["(())", "()()"]

例 2

1 組では、"()" の 1 つだけです。

n = 1

["()"]

例 3

3 組では 5 つです。辞書の順なので、( が前に多く続く物から並びます。

n = 3

["((()))", "(()())", "(())()", "()(())", "()()()"]

面接での聞かれ方

面接では、短い言葉で渡されることがよくあります。

「n 組の括弧で作れる、正しい組み合わせを全部列挙してください」
「返す順は決まっていますか？」と、自分から確かめるかを見られます
書き終えたあとに「いくつ作られますか？」と、数の伸び方を聞かれることもあります

括弧の対応を確かめる問題 (スタックで判定する問題) と組で出されることがあります。判定ではなく作る問題なので、作る途中で正しくない並びに入らないように枝を切るのが要点です。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

素直に書くなら、( と ) を 2n 文字並べる 2 の 2n 乗通りを全部作り、正しく閉じているかを 1 つずつ確かめます。n が 8 なら 6 万 5 千通りほどで、ほとんどが正しくない並びです。作ってから捨てる手間が大きくなります。

段 2

1 文字ずつ右へ伸ばしながら、正しくなくなる手前で止めます。いつ ( を置けるか、いつ ) を置けるかを決めれば、正しい並びだけを作れます。( は、使った数が n より少なければ置けます。) は、使った数が ( の使った数より少なければ置けます。

段 3

長さが 2n になったら、それは必ず正しく閉じた並びなので、答えに足します。( を先に試してから ) を試すと、( を前の文字と見た辞書の順で作られます。並べ替えは要りません。

段 4

持つ値を減らします。) の数は、いまの長さから ( の数を引けば分かるので、持つのは並びと ( の数 o の 2 つで足ります。) を置ける条件「) の数 < o」は、「いまの長さ < 2 × o」と同じです。

解答

Python

def gen_brackets(n):
    out = []

    def grow(s, o):
        if len(s) == 2 * n:
            out.append(s)
            return
        if o < n:
            grow(s + "(", o + 1)
        if len(s) < 2 * o:
            grow(s + ")", o)

    grow("", 0)
    return out

JavaScript

function genBrackets(
  n
) {
  const out = [];
  const grow = (s, o) => {
    if (s.length === 2 * n) {
      out.push(s);
      return;
    }
    if (o < n) {
      grow(s + "(", o + 1);
    }
    if (s.length < 2 * o) {
      grow(s + ")", o);
    }
  };
  grow("", 0);
  return out;
}

Go

func genBrackets(
	n int,
) []string {
	out := []string{}
	var grow func(s string, o int)
	grow = func(s string, o int) {
		if len(s) == 2*n {
			out = append(out, s)
			return
		}
		if o < n {
			grow(s+"(", o+1)
		}
		if len(s) < 2*o {
			grow(s+")", o)
		}
	}
	grow("", 0)
	return out
}

grow は、いまの並び s と、使った ( の数 o を受け取り、1 文字足して自分を呼び直します。s + "(" は新しい文字列を作るので、呼び出しから戻ったあとに文字を消して元に戻す手間が要りません。Go は関数の中で自分を呼ぶ関数を作るため、先に var grow で名前を決めてから中身を入れています。

計算量

作られる並びの数は、カタラン数と呼ばれる数です。n が 1 から 8 で、1、2、5、14、42、132、429、1430 と伸びます。おおよそ 4 の n 乗を n の 1.5 乗で割った速さで増えます
時間は、並びの数 × 2n ほどです。正しくなる手前でしか伸ばさないので、途中で捨てる枝がありません。並び 1 つを作るのに、長さ 2n の文字列を作る手間がかかります
使う記憶は、答えを除けば O(n) です。呼び出しの深さが 2n までです
段 1 の全部作って確かめる書き方は、2 の 2n 乗 × 2n ほどの手間です

よくある間違い

) を置ける条件を「) の数 < n」にする。 "())(" のような、途中で閉じすぎる並びまで作ってしまいます。比べる相手は n ではなく、いま開いている ( の数です
) を先に試す。 正しい並びは全部作れますが、順が辞書の順の逆になり、例 1 で ["()()", "(())"] を返します。( を先に試します
長さが 2n になったときに、正しいかをもう一度確かめる。決まりを守って伸ばしたので、必ず正しくなっています。確かめは要りません
並びを 1 つの配列に足し引きして作り、答えに配列をそのまま入れる。 あとで書き換わった同じ配列を何度も入れることになります。入れるときに文字列に直すか、毎回新しい文字列を作ります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def gen_brackets(n: int) -> list[str]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(gen_brackets(2))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します