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) などの小さい結果を組み合わせて作ってもかまいません。