[C]Intuitive Solution with backtracking, vector, and stack.


  • 0
    H

    If I do not want to use Binomial Coefficient to calculate the number of total Parentheses, then I put all generation in a vector string array.

    typedef struct ret_buf {
        int curr; 
        int size;
        char** ret_s;
    } ret_buf;
    
    ret_buf result;
    
    char** vector_extend(ret_buf* result);
    int gen_result(ret_buf* result, char*stk, int level, int left, int right, int max_level) {
        static int num_sols = 0;
        if(level == max_level) {
            result->ret_s = vector_extend(result);
            result->ret_s[result->curr] = malloc(1+level);
            memcpy(result->ret_s[result->curr], stk, max_level+1);
            result->curr++;
            return num_sols++;
        }
    
        if(left < max_level/2) {
            stk[level] = '(';
            gen_result(result, stk, level+1, left+1, right, max_level);
        }
    
        if(right < left) {
            stk[level] = ')';
            gen_result(result, stk, level+1, left, right+1, max_level);
        }
        
        return 0;
    }
    char** vector_extend(ret_buf* result) {
        char** tmp  = NULL;
        if(result->curr < result->size) return result->ret_s;
        result->size *= 2;
        tmp = (char**)malloc(sizeof(char*) * result->size);
        for(int i = 0; i < result->curr; i++) { 
            tmp[i] = result->ret_s[i];
        }
        free(result->ret_s);
        result->ret_s = tmp;
        return tmp;
    }
    char** generateParenthesis(int n, int* returnSize) {
        int stklen = n*2;
        char*stk = malloc(stklen+1);
        stk[stklen] = '\0';
        result.size = 8192;
        result.ret_s = (char**) malloc(sizeof(char*) * result.size);
        result.curr = 0;
    
        gen_result(&result, stk, 0, 0, 0, n*2);
        *returnSize = result.curr;
        return result.ret_s;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.