Namaran

Code daily. Without assist.

2026-11-01

parens.rs

fn balanced(n: usize) -> Vec<String> {
}

( を n 個と ) を n 個並べた文字列のうち、括弧の対応がとれているものをすべて返す balanced を書いてください。対応がとれているとは、左から読んでいくどの時点でも、それまでの ) の数が ( の数を超えないことです。( が ) より前に来る順で並べて返し、n が0なら空文字列1つだけを返します。

入力例 1

balanced(2)

出力例 1

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

入力例 2

balanced(0)

出力例 2

[""]

入力例 3

balanced(3)

出力例 3

["((()))", "(()())", "(())()", "()(())", "()()()"]
Reference
fn balanced(n: usize) -> Vec<String> {
    fn go(s: &mut String, open: usize, close: usize, n: usize, out: &mut Vec<String>) {
        if close == n {
            out.push(s.clone());
            return;
        }
        if open < n {
            s.push('(');
            go(s, open + 1, close, n, out);
            s.pop();
        }
        if close < open {
            s.push(')');
            go(s, open, close + 1, n, out);
            s.pop();
        }
    }
    let mut out = Vec::new();
    go(&mut String::new(), 0, 0, n, &mut out);
    out
}

左から1文字ずつ ( か ) を置いていき、n 組を置き終えたら結果に加えます。2 の 2n 乗通りの並びを全部作ってから対応を調べることもできますが、置いた時点で対応が崩れる並びは、その先に何を足しても直りません。そこで、置いてよい文字だけを置きます。( は、まだ n 個置いていなければ置けます。) は、それまでに置いた ) が ( より少ないときだけ置けます。

この2つの条件を守ると、作りかけの並びはどれも最後まで完成させられるので、行き詰まって捨てる候補が1つもありません。close == n になった時点で open も n なので、そこが置き終わりです。( を先に試すので、結果は ( が ) より前に来る順に並びます。作りかけの並びは1本の String を使い回し、push で試した文字は戻ったときに pop で取り除きます。clone するのは、完成した並びを結果に入れるときだけです。

掲載したのは参考実装で、唯一の正解ではありません。balanced(n - 1) などの小さい結果を組み合わせて作ってもかまいません。