MatchingParens.scala

import java.util.concurrent.LinkedBlockingDeque

/*
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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
 */

object MatchingParens extends App {
  var output = new LinkedBlockingDeque[String]()

  def parens(left: Int, right: Int, str: String): Unit = {

    // All pairs matched
    if(left == 0 && right == 0){
      output.push(str)
    }

    // while there is open parent increment close number
    if(left > 0){
      parens(left - 1, right + 1, str + "(")
    }

    // close open paren
    if(right > 0){
      parens(left, right - 1, str + ")")
    }

  }

  val n = 4

  // We start with the number of open paren and decrease down to 0 matching with closed ones
  parens(n, 0, "")

  println(output)
}