22. Generate Parentheses

Link: https://leetcode.com/problems/generate-parentheses

Description: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Solution:

Use backtracking to generate all possible combinations of parentheses. At each step, we can either add an opening or closing parenthesis as long as the number of opening parentheses is less than n and the number of closing parentheses is less than the number of opening parentheses. Duplicate parentheses are avoided by only adding a closing parenthesis if the number of opening parentheses is greater than the number of closing parentheses. The base case is when the length of the string is equal to n * 2, at which point the string is added to the results array.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let results = []

  function backtrack(s = '', left = 0, right = 0) {
    if (s.length === n * 2) {
      results.push(s)
      return
    }

    if (left < n) {
      backtrack(s + '(', left + 1, right)
    }

    if (left > right) {
      backtrack(s + ')', left, right + 1)
    }
  }
  backtrack()
  return results
}