1 /*****************************************************************************************
  2 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
  3 For example, given n = 3, a solution set is:
  4 [
  5   "((()))",
  6   "(()())",
  7   "(())()",
  8   "()(())",
  9   "()()()"
 10 ]
 11 *****************************************************************************************/
 12 #include<stdio.h>
 13 
 14 struct linklist{
 15     char *str;
 16     int flag;//记录是否剩余未配对的括号的个数
 17     int status;//记录当前使用的左括号的个数
 18     struct linklist *next;
 19 };
 20 
 21 /**
 22  * Return an linklist that is the copy of p.
 23  */
 24 struct linklist *copyParenthesisLink(struct linklist *p,int n){
 25     struct linklist *q = (struct linklist *)malloc(sizeof(struct linklist));
 26     q->str = (char *)malloc((2*n + 1)*sizeof(char));
 27     strncpy(q->str,p->str,2*n + 1);
 28     q->status = p->status;
 29     q->flag = p->flag;
 30     return q;
 31 }
 32 
 33 struct linklist *buildParenthesis(int step,int n,int *length){
 34     if(step == 0){//第一个括号
 35         struct linklist *head = (struct linklist *)malloc(sizeof(struct linklist));
 36         head->str = (char *)malloc((2*n + 1)*sizeof(char));
 37         memset(head->str,0,(2*n + 1)*sizeof(char));
 38         head->str[step] = ‘(‘;//只能为左括号
 39         head->status = 1;
 40         head->flag = 1;
 41         *length = 1;
 42         head->next = NULL;
 43         return head;
 44     }
 45 
 46     struct linklist *head = buildParenthesis(step - 1,n,length);//递归
 47     struct linklist *p = head;
 48     while(p != NULL){
 49         if(p->flag == 0){//若括号完全配对，则添加新的左括号
 50             p->status++;
 51             p->flag++;
 52             p->str[step] = ‘(‘;
 53         }else if(p->status == n){//若无可用的新的括号，则只能配对已存在的括号
 54             p->flag--;
 55             p->str[step] = ‘)‘;
 56         }else{//若为其它情况，添加左括号或右括号都可以，需要添加一个可能串
 57             struct linklist *q = copyParenthesisLink(p,n);
 58             p->status++;
 59             p->flag++;
 60             p->str[step] = ‘(‘;
 61             q->flag--;
 62             q->str[step] = ‘)‘;
 63             q->next = p->next;
 64             p->next = q;
 65             p = p->next;
 66             *length = *length + 1;
 67         }
 68         p = p->next;
 69     }
 70 
 71     return head;
 72 }
 73 
 74 /**
 75  * Return an array of size *returnSize.
 76  * Note: The returned array must be malloced, assume caller calls free().
 77  */
 78 char** generateParenthesis(int n, int* returnSize) {
 79     struct linklist *head = buildParenthesis(2*n - 1,n,returnSize);
 80 
 81     int i = 0;
 82     char **retStrs = (char **)malloc((*returnSize)*sizeof(char *));
 83   struct linklist *p = NULL;
 84   while(head != NULL){
 85       p = head;
 86       head = head->next;
 87       p->next = NULL;
 88       retStrs[i] = (char *)malloc((2*n + 1)*sizeof(char));
 89       strncpy(retStrs[i],p->str,2*n + 1);
 90       free(p->str);
 91       free(p);
 92       i++;
 93   }
 94 
 95   return retStrs;
 96 }
 97 
 98 void main(){
 99     int n = 0;
100     char **as = generateParenthesis(4,&n);
101     printf("%d\n",n);
102     for(int i = 0;i < n;i++){
103         printf("%s\n",as[i]);
104     }
105 
106     for(int i = 0;i < n;i++){
107         free(as[i]);
108     }
109 }