; coin change, part 1
(define (count xs n)
(let ((cs (make-vector (+ n 1) 0)))
(vector-set! cs 0 1)
(do ((xs xs (cdr xs)))
((null? xs) (vector-ref cs n))
(do ((x (car xs) (+ x 1))) ((< n x))
(vector-set! cs x (+ (vector-ref cs x)
(vector-ref cs (- x (car xs)))))))))
(define (coins xs n)
(let ((cs (make-vector (+ n 1) (list))))
(vector-set! cs 0 (list (list)))
(do ((xs xs (cdr xs)))
((null? xs) (vector-ref cs n))
(do ((i (car xs) (+ i 1))) ((< n i))
(vector-set! cs i
(append (vector-ref cs i)
(map (lambda (zs) (cons (car xs) zs))
(vector-ref cs (- i (car xs))))))))))
(display (count '(1 5 10 25) 40)) (newline)
(for-each (lambda (x) (display x) (newline))
(coins '(1 5 10 25) 40))