(defparameter *all-partitions* nil)

(defun lookup-partition (n k)
  (let ((partitions-of-n (gethash n *all-partitions*)))
    (when partitions-of-n
      (gethash k partitions-of-n))))

(defun store-partition (n k partition)
  (unless (lookup-partition n k)
    (let ((partitions-of-n (gethash n *all-partitions*)))
      (unless partitions-of-n
	(setf (gethash n *all-partitions*) (make-hash-table))
	(setf partitions-of-n (gethash n *all-partitions*)))
      (setf (gethash k partitions-of-n) partition))))
 
(defun cons-tuples (k tuples)
  (mapcar (lambda (tuple) (cons k tuple)) tuples))

(defun partitions (n k partitions) 
  (if (or (< n 0) (= k 0)) (return-from partitions nil))
  (if (= n 0)  (return-from partitions (list (list))))
  (let ((partition (lookup-partition n k))) ; look up memoized result?
    (unless partition 
      (setf partition (append (cons-tuples k (partitions (- n k) k partitions))
			      (partitions n (- k 1) partitions)))
      (store-partition n k partition))  
    partition)) 

(defun main (n)
  (setf *all-partitions* (make-hash-table))
  (let ((partitions (partitions n n nil)))
    (format t "p(~A) = ~A~%" n (length partitions))
    (mapcan (lambda (p) (format t "~A~%" p)) partitions)))


CL-USER> (main 6)
p(6) = 11
(6)
(5 1)
(4 2)
(4 1 1)
(3 3)
(3 2 1)
(3 1 1 1)
(2 2 2)
(2 2 1 1)
(2 1 1 1 1)
(1 1 1 1 1 1)