002.md

002 - Encyclopedia of Parentheses (★3)

解答

bit 全探索により、すべてのパターンを列挙して調べます。

例: N = 4 のとき

カッコ列
((((	0	0	0	0
((()	0	0	0	1
(()(	0	0	1	0
(())	0	0	1	1
()((	0	1	0	0
()()	0	1	0	1
())(	0	1	1	0
()))	0	1	1	1
)(((	1	0	0	0
)(()	1	0	0	1
)()(	1	0	1	0
)())	1	0	1	1
))((	1	1	0	0
))()	1	1	0	1
)))(	1	1	1	0
))))	1	1	1	1

#include <iostream>

int main()
{
	// 長さ N のカッコ列
	int N;
	std::cin >> N;

	// 例えば N = 4 のとき
	// 0b0000 ～ 0b1111 について調べる
	for (int i = 0; i < (1 << N); ++i)
	{
		// カッコのネスト数
		// '(' で 1 増え, ')' で 1 減る
		int nest = 0;

		// 最上位のビットから調べていく
		for (int k = (N - 1); k >= 0; --k)
		{
			// bit フラグが 0 なら '(', 1 なら ')'
			const char c = ((i & (1 << k)) == 0) ? '(' : ')';

			if (c == '(')
			{
				++nest;
			}
			else
			{
				--nest;

				if (nest < 0) // ネスト数が 0 未満になるのは違反
				{
					break;
				}
			}
		}

		// ネスト数が 0 で終わっていれば正しい
		if (nest == 0)
		{
			// 解答を出力
			for (int k = (N - 1); k >= 0; --k)
			{
				const char c = ((i & (1 << k)) == 0) ? '(' : ')';

				std::cout << c;
			}

			std::cout << '\n';
		}
	}
}