Leetcode——Generate Parenthese

问题描述：        

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

        针对一个长度为2n的合法排列，第1到2n个位置都满足如下规则：左括号的个数大于等于右括号的个数。所以，我们就可以按照这个规则去打印括号：假设在位置k我们还剩余left个左括号和right个右括号，如果left>0，则我们可以直接打印左括号，而不违背规则。能否打印右括号，我们还必须验证left和right的值是否满足规则，如果left>=right，则我们不能打印右括号，因为打印会违背合法排列的规则，否则可以打印右括号。如果left和right均为零，则说明我们已经完成一个合法排列，可以将其打印出来。

        这个题第一眼看上去就应该使用递归来解决，然而Leetcode给处的函数原形是这样的：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        
    }
};

         我只想说卧槽，在这种情况下把结果作为函数的返回值返回臣妾真心做不到啊！默默地把代码写成了这样：

void generate(int count1, int count2, string current, int n, vector<string>& combinations)
{
	if (count1 == n && count2 == n)		//扫描完了
	{
		combinations.push_back(current);
	}
	else {
		if (count1 < count2) {
			return;
		}
		//打印左括号
		if (count1 < n)
		{
			generate(count1 + 1, count2, current + "(", n, combinations);
		}
		//打印右括号
		if (count1 > count2 && count1 <= n)
		{
			generate(count1, count2 + 1, current + ")", n, combinations);
		}
	}
}

class Solution 
{
public:
	vector<string> generateParenthesis(int n) 
	{
		string current = "";
		generate(0, 0, current, n, combinations);
		
		return combinations;
	}
	vector<string> combinations;
};

Leetcode——Generate Parenthese

原文：http://my.oschina.net/u/1047616/blog/529160