[AtCoder] [經典競程 90 題] 002 - Encyclopedia of Parentheses（★3）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_b
題目大意:
給你一個 $N$ ，請輸出所有長度為 $N$ 且合法括號序列。

---

這題其實跟 LeetCode 22 一模一樣，不過我真的做不太出來，上次面試被問還真的寫錯東西...
總之，這裡的做法是因為我們知道把「(」當作 $+1$、「)」當作 $-1$ 的話，一個括號序列合法，若且唯若前綴和恆非負且總和為 $0$。於是我們就可以暴力遞迴下去，每次都加加看右括號或左括號，並檢查當前的和是不是少於 $0$ 了，最後長度滿足後就把構造的序列加入 set 裡即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;

	if (n & 1) return 0;

	set<string> ans;

	auto generate = [&ans](auto rec, int lef, int rig, string s) -> void {
		if (rig < lef or lef < 0 or rig < 0) return;
		if (lef == 0 and rig == 0) {
			ans.insert(s);
			return;
		}
		rec(rec, lef - 1, rig, s + "(");
		rec(rec, lef, rig - 1, s + ")");
	};
	generate(generate, n/2, n/2, "");

	for (auto s: ans) cout << s << '\n';
	return 0;
}