package main
import (
  "strings"
  "container/list"
)
/*
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
  ()()(); (())();  ((())); 
  ()(());
  (()())

Input: n = 1
Output: ["()"]
 
  ()(); (())

Constraints:

1 <= n <= 8
*/

func rec(input []string, left int, right int, n int, ans *[]string) {

  if len(input) == 2*n {
    *ans = append(*ans, strings.Join(input, ""))
    return
  }
  if left < n {
    input = append(input, "(")
    rec(input, left+1, right, n, ans)
    input = input[0:len(input)-1]
  }
  if right < left {
    input = append(input, ")")
    rec(input, left, right+1, n, ans)
    input = input[0:len(input)-1]
  }
}

func generateParenthesis(n int) []string {
  var output = make([]string, 2*n)
  var input = make([]string, 2*n)
  rec(input, 0, 0, n, &output)
  return output
}
func main() {
  generateParenthesis(3)
}