学步园

输出n对括号的所有有效组合。

思路：

运用递归的思想。只要左括号没有用完，总可以插入左括号；当已插入的左括号数目大于右括号，那么就可以插入右括号。我们只要记录左右括号剩余的数目，然后递归即可。递归终止条件有两个：当左括号剩余数小于0或者左括号剩余数大于右括号剩余数，此时为无效状态；当左右括号剩余数都为0，此时输出结果。

#include <iostream>
#include <vector>
using namespace std;

void Pare(vector<char>& s, int l, int r, int c)
{
	if (l < 0 || r < l)
		return;
	if (l == 0 && r == 0)
	{
		for (int i = 0; i < s.size(); ++i)
			cout << s[i];
		cout << endl;
	}
	else
	{
		if (l > 0)
		{
			s[c] = '(';
			Pare(s, l - 1, r, c + 1);
		}
		if (r > l)
		{
			s[c] = ')';
			Pare(s, l, r - 1, c + 1);
		}
	}
}

void main()
{
	int c = 4;
	vector<char> vec(2*c);
	Pare(vec, c, c, 0);
}