22. Generate Parentheses

Problem

https://leetcode.com/problems/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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

The total number of the results is Catalan number but it doesn't matter in this problem.

• Consider every position must be left or right parenthesis.
• "n pairs of parentheses" means n left parentheses and n right.
• But to every pair of parentheses there should be left first then right, which means the amount of unused left parentheses should always be less or equal than the unused right parentheses.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let results = []

    gen(n, n, '')

    function gen(lNum, rNum, str) {
        if (lNum > rNum) { return }

        if (lNum === 0 && rNum === 0) {
            results.push(str)
            return
        }

        if (lNum > 0) { gen(lNum-1, rNum, str+'(') }
        if (rNum > 0) { gen(lNum, rNum-1, str+')') }
    }

    return results
};