程序员面试金典-括号配对

实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）。

输入 ：3
输出 ：((())) (()()) (())() ()(()) ()()() （第230页）

输入很简洁，输入的n表示要打印n对括号的全部有效组合
可以考虑用递归求解：
	1.n是数据的规模，当n足够小时很容易解决
	2.当n为1时，也就是()这种情况，此时只有一种，也就是出口
	3.n大于1的时候，要考虑括号的插入位置：
		3.1可以插入到当前括号的左侧
		3.2可以插入到当前括号的右侧
		3.3可以插入到当前括号的两侧，即左右各一个
	4.考虑到插入过程中有重复的情况，引入set，去重
	5.对set遍历需要用到迭代器
	

#include
#include
#include
using namespace std;
set parenthesis(int n) {
	set res;//保存上次迭代状态
	res.insert("()");//初始状态只有一对括号
	if (n == 1) {
		return res;//n为1时直接返回
	}
	for (int i = 2; i <= n; i++) {//n大于2时
		set res_new;//创建辅助空间
		set::iterator it = res.begin();//迭代器
		for (; it != res.end(); it++) {
			//向res_new中插入括号，插入的位置分别是左侧，右侧，还有两头
			res_new.insert(*it + "()");
			res_new.insert("()" + *it);
			res_new.insert("(" + *it + ")");
		}
		res = res_new;//更新res
	}
	return res;//返回res
}
set parenthesis1(int n) {
	set s_n;
	if (n == 1) {
		s_n.insert("()");//插入括号
		return s_n;
	}
	//递归求解n-1情况
	set s_n_1 = parenthesis1(n - 1);
	set::iterator it = s_n_1.begin();//迭代器
	for (; it != s_n_1.end(); it++) {
		s_n.insert("()" + *it);
		s_n.insert(*it + "()");
		s_n.insert("(" + *it + ")");
	}
	return s_n;
}

int main()
{
	int n;
	cin >> n;
	set se = parenthesis(n);
	set::iterator it = se.begin();
	for (; it != se.end(); it++)
		cout << *it << " ";
	cout << endl;
	se = parenthesis1(n);
	it = se.begin();
	for (; it != se.end(); it++)
		cout << *it << " ";
	cout << endl;
	return 0;
}