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;
};