【題解】Zerojudge a229 - 括號匹配問題

題目連結

題目大意

輸出 $n$ 組括號的所有合法匹配組合。

題解

用 dfs 枚舉每個位置要放左括號 '(' 或是右括號 ')'。如果只有這樣做的話極有可能會吃 TLE，因此我們需要一些剪枝。觀察到如果右括號在某個時候比左括號多，或是左括號的數量大於 $n$，那麼他一定是一個不合法的括號匹配，因此可以直接剪枝剪掉。剩下實作的細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while(cin >> n) {
		auto dfs = [&](auto self, string& s, int lhs, int rhs) -> void {
			if(lhs < rhs || lhs > n) {
				return;
			}
			if(lhs + rhs == 2 * n) {
				cout << s << "\n";
				return;
			}
			s[lhs + rhs] = '(';
			self(self, s, lhs + 1, rhs);
			s[lhs + rhs] = ')';
			self(self, s, lhs, rhs + 1);
		};
		string s(2 * n, '_');
		dfs(dfs, s, 0, 0);
		cout << "\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a229 - 括號匹配問題