某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
void parenthesis(int l, int r, string& s, vector<string>& ans) {
if (l + r == 0) {
ans.push_back(s); return;
}
if (r < l) return;
if (l > 0) {
s.push_back('(');
parenthesis(l - 1, r, s, ans);
s.pop_back();
}
if (r > 0) {
s.push_back(')');
parenthesis(l, r - 1, s, ans);
s.pop_back();
}
}
(呼出の例) vector<string> ans; string s; parenthesis(4, 4, s, ans);
この if (r < l) return; が左右のバランス(単に'('と')'の数が同じというだけでなく)の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが
どなたかわかりやすい説明はないでしょうか
ニュース
- 【野球】松井秀喜氏が巨人新監督に決定 きょう午後会見 [THE FURYφ★]
- 松井秀喜氏が巨人新監督に決定 きょう午後会見 [ぐれ★]
- 「一人で登りたいのに」女性登山者についてくる“おじさん”、「迷惑」「怖い」の声…罪にならないの? [少考さん★]
- デジタル庁HPの問い合わせ内容漏洩か 最大1万3000件以上 [ぐれ★]
- 【小説家】平野啓一郎、「ネト◯ヨ」と日本について投稿 [少考さん★]
- 「ブサイクな金持ち」と「貧乏イケメン」、女性はどっちを選ぶのか マッチングアプリが明らかにした“残酷すぎる結論”★2 [♪♪♪★]
- 巨人、松井秀喜監督就任
- 【緊急】安倍Guardを発動しろ🚨🚨🚨【スクリプト襲来】 [398632733]
- 【訃報】キオクシア、大暴落 [982893389]
- 【悲報】嫌儲、安倍スクリプトでもう無茶苦茶 [589647274]
- 黒い物があると思ったらカラスが亡くなってる…😱
- 朝から醤油ラーメンだよ🍜高市さん!! [457294144]