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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析
生成括号对，只需要用递归的方法即可。最大的数组大小可以采用int较大的数值。
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void generate(char**ans,int*returnSize,int n,int left,int right,char *temp,int length)
{
//printf("%d %d %d %s\n",left,right,length,temp);
if(length==2*n)
{
temp[length]='\0';
//printf("%d %s\n",*returnSize,temp);
ans[(*returnSize)]=(char*)malloc(sizeof(char)*(2*n+1));
for(int i=0;i<length;i++)
ans[*returnSize][i]=temp[i];
ans[(*returnSize)][length]='\0';
*returnSize=*returnSize+1;
return;
}
if(left<n)
{
temp[length]='(';
length++;
left++;
generate(ans,returnSize,n,left,right,temp,length);
length--;
left--;
}
if(left>right)
{
temp[length]=')';
length++;
right++;
generate(ans,returnSize,n,left,right,temp,length);
length--;
right--;
}
return;
}
char** generateParenthesis(int n, int* returnSize) {
int max=1000000;
//for(int i=2;i<=3*n;i++)
// max=max*i;
char **ans=(char**)malloc(sizeof(char*)*max);
char*temp=(char*)malloc(sizeof(char)*(2*n+1));
*returnSize=0;
generate(ans,returnSize,n,0,0,temp,0);
return ans;
}
