Generate Parentheses

Problem

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

Solution

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res = [];
    backtrack(res, "", n, 0, 0);
    return res;
};

var backtrack = function(res, path, total, numOpen, numClose) {
    if (path.length === total * 2) {
        res.push(path);
    } else {
        if (numOpen < total) {
            backtrack(res, path + "(", total, numOpen + 1, numClose);
        }
        if (numOpen > numClose) {
            backtrack(res, path + ")", total, numOpen, numClose + 1);
        }
    }
};

We will implement a backtracking (DFS) solution. We keep track of the number of opening brackets numOpen and the number of closing brackets numClose in path. Using this information, we add opening and closing brackets to path recursively, while ensuring the generated parentheses are well-formed.

For example, if n = 2, res changes in the following order: [] => ["(())"] => ["(())", "()()"].

Problem​

Solution​

Problem

Solution