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

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

(defun generate-parentheses (number-of-parentheses)
  (let ((stack (make-empty-vector 0))
	(result (make-empty-vector 0)))
    (labels ((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))
    result))