22. Generate Parentheses

题目：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:

[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

思路：

深搜题，重点是剪枝：字符串从头到任意位置处的)不得多于(数量，dfs的参数(string s, int l, int r,int &n)分别为当前字符串s，使用了l个‘(’，使用了r个’)’，一共有n对括号。
①‘(’和‘)’各使用了n个，完成符合条件的字符串，加入res.
②’(‘使用了n个而’)'不足n个，在字符串后增加)且r+1.
③l=r<n，此时只能增加(。
④l<r<n，此时可以增加(也可以增加)；

代码

vector<string> res;

void dfs(string s, int l, int r,int &n) {
	if (l == n&&r == n) {
		res.push_back(s);
		return;
	}	
	if (l == n) {
		dfs(s + ')', l, r + 1, n);
		return;
	}
	if (l < n) {
		dfs(s + '(', l + 1, r, n);
		if (l > r)
			dfs(s + ')', l, r + 1, n);
	}
}

vector<string> generateParenthesis(int n) {
	res.clear();
	dfs(string(), 0, 0, n);
	return res;
}