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

problem_8.ts

function recurse(current: string, remaining: { left: number; right: number; }) {
  if (remaining.left === 0 && remaining.right === 0) {
    return [current]
  } else {
    let result = []
    // check if we can go with a "("
    if (remaining.left) {
      let balance = 0
      for (const s of current) {
        if (s === '(') {
          balance++
        } else {
          balance--
        }
      }
      if (balance + 1 <= remaining.right) {
        result.push(...recurse(current + '(', { left: remaining.left - 1, right: remaining.right }))
      }
    }

    // check if we can go with a ")"
    if (remaining.right) {
      let balance = 0
      for (const s of current) {
        if (s === ')') {
          balance++
        } else {
          balance--
        }
      }
      if (balance + 1 <= remaining.left && balance + 1 <= 0) {
        result.push(...recurse(current + ')', { left: remaining.left, right: remaining.right - 1 }))
      }
    }
    return result
  }
}

function generateParenthesis(n: number): string[] {
  return recurse('(', { left: n - 1, right: n })
};