(defun make-empty-vector ()
  (make-array 0 :fill-pointer 0 :adjustable t))

(defun vector-join (vector)
  (format nil 
          (concatenate 'string "~{~a~^~}")
	  (coerce vector 'list)))

(defun generate-parentheses (number-of-parentheses)
  (let ((stack (make-empty-vector))
	(result (make-empty-vector)))
    (defun backtrack (open-parentheses closed-parentheses)
      (when (= open-parentheses
	       closed-parentheses
	       number-of-parentheses)
	(vector-push-extend (vector-join stack) result)
	(return-from backtrack))

      (when (< open-parentheses number-of-parentheses)
	(vector-push-extend "(" stack)
	(backtrack (1+ open-parentheses) closed-parentheses)
	(vector-pop stack))

      (when (< closed-parentheses open-parentheses)
	(vector-push-extend ")" stack)
	(backtrack open-parentheses (1+ closed-parentheses))
	(vector-pop stack)))
    (backtrack 0 0)
    (return-from generate-parentheses result)))

(generate-parentheses 3)