LeetCode: Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

---

Use recursive function to generate each possible string. When there is no open parenthesis, add 1, when the current number of close parenthesis is less than the number of open parenthesis, add one close parenthesis.

C++ Code:

/*
 * func: generate_parenthesis_helper
 * goal: use recrusion to generate each combination
 * @param result: final sets of results
 * @param left_parenthesis: the number of left parenthesis
 * @param right_parenthesis: the number of right parenthesis
 * @param str: current string
 * return: void
 */
void generate_parenthesis_helper(vector<string> &result, int left_parenthesis, int right_parenthesis, string str){
    if(left_parenthesis == 0 && right_parenthesis == 0){
        result.emplace_back(str);
        return;
    }
    
    if(left_parenthesis > 0){
        generate_parenthesis_helper(result, left_parenthesis-1, right_parenthesis + 1, str + "(");
    }
    
    if(right_parenthesis > 0){
        generate_parenthesis_helper(result, left_parenthesis, right_parenthesis-1, str + ")");
    }
}

/*
 * func: generate_parenthesis
 * goal: generate n pairs of parenthesis and they are all well formed
 * @param n: the number of pairs
 * return: all possible pairs
 */
/*
 * Use DFS
 */
vector<string> generate_parenthesis(int n){
    vector<string> result;
    generate_parenthesis_helper(result, n, 0, "");
    return result;
}

Python Code:

# func: recursive function to help generating pairs of parenthesis
# @param result: final result list
# @param left_parenthesis: number of left parenthesis in current string
# @param right_parenthesis: number of right parenthesis in current string
# @param num: total number of pairs
# @param str: current string
# @return: nothing
def generate_parenthesis_helper(result, left_parenthesis, right_parenthesis, num, str):
    if left_parenthesis == num and right_parenthesis == num:
        result.append(str)
        return
    if left_parenthesis < num:
        generate_parenthesis_helper(result, left_parenthesis+1, right_parenthesis, num, str+'(')
    if right_parenthesis < left_parenthesis <= num:
        generate_parenthesis_helper(result, left_parenthesis, right_parenthesis+1, num, str+')')

# func: to generate all possible n pairs of parenthesis
# @param n: the number of pairs
# @return: return a list of possible pairs
def generate_parenthesis(n):
    if n <= 0:
        return []
    else:
        result = []
        generate_parenthesis_helper(result, 0, 0, n, '')
        return result