Generate Parentheses
Description
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(javascript)
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
const output = [];
const dfs = (str, open, close) => {
// Close parentheses can not be more than open parentheses at any
// given time to stay valid.
if (open > close) {
return;
}
// Base case. We now have n pairs of parentheses
if (open === 0 && close === 0) {
output.push(str);
return;
}
// Insert open parenthsis and search for the next valid insertion.
if (open > 0) {
dfs(`${str}(`, open - 1, close);
}
// Insert close parenthsis and search for the next valid insertion.
if (close > 0) {
dfs(`${str})`, open, close - 1);
}
};
dfs('', n, n);
return output;
};