22. Generate Parentheses

Problem:

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

ONE

Recursive DFS backtracking.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
  const result = []
  if (n > 0) {
    dfs(n, 0, 0, '', result)
  }
  return result
};

function dfs (n, nopen, nclose, path, result) {
  if (path.length === n * 2) {
    result.push(path)
    return
  }

  if (nopen < n) {
    dfs(n, nopen + 1, nclose, path + '(', result)
  }

  if (nclose < nopen) {
    dfs(n, nopen, nclose + 1, path + ')', result)
  }
};

TWO

BFS.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
  if (n <= 0) { return [] }

  const queue = [{
    path: '(',
    open: 1,
    close: 0,
  }]

  while (true) {
    const { path, open, close } = queue.shift()
    if (open + close === n * 2) {
      queue.unshift({ path, open, close })
      break
    }

    if (open < n) {
      queue.push({
        path: path + '(',
        open: open + 1,
        close,
      })
    }

    if (close < open) {
      queue.push({
        path: path + ')',
        open,
        close: close + 1,
      })
    }
  }

  return queue.map(x => x.path)
};