Description
Generate Parentheses
MediumGiven 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
Solutions
This function generates all balanced parentheses strings of length 2n through depth-first search. The dfs helper carries cur (the string so far), open (how many "(" are currently unmatched), and toOpen (how many "(" still need to be placed). It recurses by adding a ")" whenever open > 0 and by adding a "(" whenever toOpen > 0, which guarantees every intermediate string stays valid. When open + toOpen === 0, there are no brackets left to open or close, so cur is complete and is pushed into the res array. Since the rules prevent duplicates, a plain array is enough here, and res is returned after dfs("", 0, n) has explored every path.
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
let res = [];
const dfs = (cur, open, toOpen) => {
if (open > 0) dfs(cur + ')', open - 1, toOpen);
if (toOpen > 0) dfs(cur + '(', open + 1, toOpen - 1);
if (open + toOpen === 0) res.push(cur);
};
dfs('', 0, n);
return res;
};