(define ht (make-hashtable equal-hash equal?))

(define (count-change-crappy sum . coins)
  (cond
    ((= sum 0) 1)
    ((or (null? coins) (< sum 0)) 0)
    (else
      (+ (apply count-change-crappy (cons sum (cdr coins)))
         (apply count-change-crappy (cons (- sum (car coins)) coins)))
    )
  )
)

(define (count-change-memoized sum . coins)
  (cond
    ((= sum 0) 1)
    ((or (null? coins) (< sum 0)) 0)
    (else
      (let ((key1 (cons sum (cdr coins)))
           (key2 (cons (- sum (car coins)) coins)))
        (if (not (hashtable-contains? ht key1))
          (hashtable-set! ht key1 (apply count-change-memoized key1))
        )
        (if (not (hashtable-contains? ht key2))
          (hashtable-set! ht key2 (apply count-change-memoized key2))
        )
        (+ (hashtable-ref ht key1 0)
           (hashtable-ref ht key2 0))
      )
    )
  )
)

(define (time f . args)
  (define before (js-invoke (js-new "Date") "getTime"))
  (define result (apply f args))
  (define after (js-invoke (js-new "Date") "getTime"))
  (print "Ran for " (- after before) " ms, Number of combinations: " result)
)

(time count-change-memoized 100 1 2 3 6 9)
(time count-change-crappy 100 1 2 3 6 9)