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;
}