generate-parentheses

Generate Parentheses

The 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:

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

The Idea

Not a lot of thought here. Just the idea that 3 parens is simply all the combinations returned by 2 parens and then surrounded by parentheses., prepended by parentheses., and appended with parentheses. Just de-dupe the entire thing and we’re done.

Implementation

Racket

(require racket/generator)
(require racket/format)

(define (parens-combos n)
  (in-generator
   (let recur ([prefix ""]
               [n n]
               [suffix ""])
     (define (again new-prefix new-suffix)
       (recur (~a prefix new-prefix) (sub1 n) (~a new-suffix suffix)))
     (cond 
       [(< n 1) (yield (~a prefix suffix))]
       [(eq? n 1) (again "()" "")]
       [else (again "(" ")")
             (again "()" "")
             (again "" "()")]))))

(list->set (sequence->list (parens-combos 3)))

(set "(())()" "((()))" "()(())" "()()()" "(()())")

Javascript

const parensCombos = function * (n) {
    if(n < 1)
        return
    if(n === 1) {
        yield `()`
        return
    }
    for(const innerCombo of parensCombos(n-1)) {
        yield `(${innerCombo})`
        yield `()${innerCombo}`
        yield `${innerCombo}()`
    }
}

return [...new Set(parensCombos(3))]

((()))

()(())

(())()

(()())

()()()