JSFiddle - React, Tailwind, and code Playground

by sperske

JavaScript

const cache = new Map()

function cacheKey(n, parens) {
  return n + parens.join('')
}

function allBalancedStrings(n, parens = ['(', ')']) {
  if (n === 0) return ['']
  const result = []
  const cached = cache.get(cacheKey(n, parens))
  if (cached) return cached

  for (let i = 0; i < n; i++) {
    for (const s1 of allBalancedStrings(i, parens)) {
      for (const s2 of allBalancedStrings(n - i - 1, parens)) {
        result.push(`${parens[0]}${s1}${parens[1]}${s2}`)
      }
    }
  }
  cache.set(cacheKey(n, parens), result)
  return result
}

for (let i = 1; i < 18; i++) {
  console.log(i, [...allBalancedStrings(i)].length)
}
console.log([...allBalancedStrings(4, ['{', '}'])])