CC150 9.6

9_6.cpp

/* CC150 9.6 */
// valid combinations of n pairs of parentheses

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void generateParens(string paren, int leftCap, int rightCap, vector<string> &parenList)
{
	if (leftCap == 0 && rightCap == 0) {
		parenList.push_back(paren);
		return;
	}
	if (leftCap) {
		paren.push_back('(');
		generateParens(paren, leftCap - 1, rightCap, parenList);
		paren.pop_back();
	}
	if (rightCap > leftCap) {
		paren.push_back(')');
		generateParens(paren, leftCap, rightCap - 1, parenList);
		paren.pop_back();
	}
}

vector<string> generateParens(int n)
{
	vector<string> parenList;
	if (n == 0)
		return parenList;
	string paren;
	generateParens(paren, n, n, parenList);
	return parenList;
}

// Catalan number C_n = C(2n,n)/(n+1) = (2n)!/((n+1)!n!) = (n+2)/2 * (n+3)/3 * ... * (2n)/(n)
// C_n is the number of "Dyck words" of length 2n, e.g. the number of expressions containing n pairs
// of parentheses which are correctly matched.
// maximum: C15 = 9694845
unsigned long long int catalan(int n) {
	unsigned long long int numerator = 1, denominator = 1;
	for (int i = 2; i <= n; ++i) {
		numerator *= (n + i);
		denominator *= i;
	}
	return numerator / denominator;
}

int main()
{
	int n;
	cin >> n;
	vector<string> parens = generateParens(n);
	for (auto paren : parens)
		cout << paren << endl;
	cout << parens.size() << " ways." << endl;
	cout << catalan(n) << " ways (catalan)." << endl;
	return 0;
}

output

4
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
14 ways.
14 ways (catalan).