22. Generate Parentheses

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

Accepted
781,434
Submissions
1,168,852

Runtime: 68 ms, faster than 96.95% of JavaScript online submissions for Generate Parentheses.
Memory Usage: 40.4 MB, less than 32.27% of JavaScript online submissions for Generate Parentheses.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];
    const max = n * 2;
    function backtrace(str, open, close) {
        if (str.length === max) {
            result.push(str);
            return;
        }
        if (open < n) {
            backtrace(str + '(', open + 1, close);
        }
        if (close < open) {
            backtrace(str + ')', open, close + 1);
        }
    }
    backtrace('', 0, 0);
    return result;
};