LeetCode 22. Generate Parentheses ( C ) – Medium

題目為給定一個數字 n ，列出 n 組 ( ) 的所有排列方式。

原文題目如下

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:

Input: n = 1
Output: ["()"]
 
Constraints:

1 <= n <= 8

解題策略為透過遞迴 ( Recursion ) ， 添加 ‘ ( ‘ 與 ‘ ) ‘ ， 添加 ‘ ( ‘ 時檢查數目是否過半 ，添加 ‘ ) ‘ 時檢查是否超過 ‘ ( ‘ 的數目。

下面是我的程式碼

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

char **relist;
int total,base;

void RGenerate(char *tempstr,int position,int leftnum,int rightnum,int max){
    
    if(position == max){
        tempstr[position] = '\0';                       // End String
        if(total==base){
            base*=2;
            relist=realloc(relist,sizeof(char *)*base);
        }
        relist[total] = (char*)malloc(max+1);
        strcpy(relist[total],tempstr);
        total++;
    }
    
    if(leftnum < (max/2)){
        tempstr[position] = '(';
        RGenerate(tempstr,position+1,leftnum+1,rightnum,max);
    }
    if(rightnum<leftnum){
        tempstr[position] = ')';
        RGenerate(tempstr,position+1,leftnum,rightnum+1,max);
    }
}

char ** generateParenthesis(int n, int* returnSize){
    total = 0;
    base = 8;
    relist = (char**)malloc(sizeof(char*)*base);
    char *tempstr = (char*)malloc(sizeof(char)*n*2+1);
    RGenerate(tempstr,0,0,0,n*2);
    (*returnSize) = total;
    return relist;
}

下面是時間與空間之消耗

Runtime: 0 ms, faster than 100.00% of C online submissions for Generate Parentheses.

Memory Usage: 6.4 MB, less than 95.68% of C online submissions for Generate Parentheses.

下一題連結 : LeetCode 23. Merge k Sorted Lists ( C ) – Hard

方便的話請幫我點選網頁四周的廣告，一點點鼓勵是我繼續寫的動力