Cassidy's Interview Question - 13/04

generateParenthesis.clj

(require '[clojure.math.combinatorics :as combo]
         '[clojure.string :as str])

(defn validParenthesis?
  "Returns true if a sequence of parentheses are balanced"
  [coll]
  (loop [parens_list (apply list coll)
         stack []]
    (if (empty? parens_list)
      (empty? stack)
      (if (= (peek parens_list) "(")
        (recur (rest parens_list) (conj stack (peek parens_list)))
        (if (empty? stack)
          (recur (rest parens_list) stack)
          (recur (rest parens_list) (rest stack)))))))

(defn generateParens
  "Returns a list of valid combinations of parentheses that
  can be formed with n parenthesis"
  [n]
  (let [openParens (repeat n "(")
        closedParens (repeat n ")")
        allParens (concat openParens closedParens)
        parensPerms (combo/permutations allParens)]
    (map #(str/join #"" %) (filter validParenthesis? parensPerms))))

(generateParens 3)