Coin Change Algorithm with limited coins - Scheme

Question

i need to write the procedure change which gets a sum of money and list of available coins, and returns the number of possible ways to pay the money with these coins. And as i said, the coins are limited.

Examples:

(change 10 '(5 5 10)) → 2
;; [1 coin of 10 ,2 coins of 5]

(change 5 '(1 1 1 2 2 5 10)) → 3
;; [1 coin of 5, 1 coin of 2 and 3 coins of 1, 2 coins of 2 and 1 coin of 1]

I tried this:

(define (change sum coins)
  (if (< sum 0)
      0
      (if (= sum 0)
          1
          (if (and (> sum 0) (<= (length coins) 0))
            0
            (+ (change (- sum (car coins)) (cdr coins)) 
               (change sum (cdr coins)))))))

But i couldn't get rid of some duplicates counts... instead of 3, my output for the 2nd example was:

(change 5 '(1 1 1 2 2 5 10)) → 6

What can be done to fix this problem?

(The code should be run in Racket, purely functional and not using any build-in methods. I prefer recursive. The only data structures that allowed are List and Pair)

Answer 1

Done it! My algorithm was simple, using this remove-all method:

(define remove-all
  (lambda (x lst)
    (if (empty? lst)
        '()
    (if (= (car lst) x)
        (remove-all x (cdr lst))
    (cons (car lst) 
          (remove-all x (cdr lst)))))))

(define payment
    (lambda (n coins-lst)
        (if (< n 0)
            0
        (if (= n 0)
            1
        (if (and (> n 0) (empty? coins-lst))
            0
        (+ (payment  (- n (car coins-lst))  (cdr coins-lst)) 
           (payment n (remove-all (car coins-lst) coins-lst))))))))

Thanks for all your advice!