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:

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

 

思路：给定整数n，要写出合法的括号字符串。假设其中一个合法字符串为str，开始时str为空，需要填充left个”(”和right个”)”，其中left=right=n。

填充”(”后，left--，填充”)”之后，right--。只要left>0，就可以填入”(”，但是在填入”)”时有更严格的条件：right>0并且right>left。right>left表明该”)”已经有对应的”(”填充了。代码如下：

//对于n，结果集的最大值，就是针对n-1的
//结果集中的每一个结果，在其中的每个'(' 的
//前后，都增加一个"()"。
int getreslen(int n)
{
	if(n == 1)	return 1;

	return 2 * (n-1) * getreslen(n-1);
}

void getres(int left, int right, char *oneres, int oneresindex, char **res, int *index)
{	
	if(left == 0 && right == 0)
	{
		char *buf = calloc(strlen(oneres)+1, sizeof(char));
		sprintf(buf, "%s", oneres);
		res[*index] = buf;
		(*index)++;
		return;
	}

	if(left > 0)
	{
		oneres[oneresindex] = '(';
		getres(left-1, right, oneres, oneresindex+1, res, index);
	}

	if(right > 0 && right > left)
	{
		oneres[oneresindex] = ')';
		getres(left, right-1, oneres, oneresindex+1, res, index);
	}
}

char** generateParenthesis(int n, int* returnSize) 
{
	char **resn;
	int sizen = 0;
	int curindex = 0;

	sizen = getreslen(n);
	resn = calloc(sizen, sizeof(char *));

	char *oneres = calloc(2*n+1, sizeof(char));

	getres(n, n, oneres, 0, resn, &curindex);
	
	*returnSize = curindex;

	free(oneres);
	return resn;
}