- 328 名前：デフォルトの名無しさん mailto:sage [2023/06/06(火) 11:53:03.19 ID:MhCqkbZk0.net]
- 某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが
どなたかわかりやすい説明はないでしょうか
|
 |
