换零钱

用100元来换若干面值的零钱（1，5，10，25，50），有多少种兑换方式？

思路

定义一个函数\(f(amount,coins)\)，用来计算使用coins来换amount的方案数量。很容易得到，分为两种情况

1. 使用零钱A（至少使用1次A）
2. 不使用零钱A

情况1，至少使用1次A，coins来兑换amount 等价于 至少使用0次A，coins来兑换(amount-A) 等价于 coins来兑换(amount-A) ，可以表示为 f(amount-coins[0],coins)

情况2，不实用零钱A，可以从coins中移除掉A，表示为 f(amount,coins[1:])

得到如下等式：

f(amount,coins) = f(amount-coins[0],coins) + f(amount,coins[1:])

递归退出

1. 当可供使用的零钱列表coins已经为空
   1. 还需要兑换的金额amount为0，说明该路径兑换成功
   2. amount不为0，说明兑换失败
2. coins不为空
   1. 当需要兑换的金额amount为负数的时候，说明该情况下兑换已经失败了。
   2. amount非负，继续兑换

代码

func change(amount int, coins []int) int {
	if len(coins) == 0 {
		if amount != 0 {
			return 0
		} else {
			return 1
		}
	}
	if amount < 0 {
		return 0
	}
	return change(amount-coins[0], coins) + change(amount, coins[1:])
}

(define (change amount coins)
  (cond ((= 0 (length coins))
         (if (= 0 amount)
             1
             0))
        ((> 0 amount) 0)
        (else (+ (change (- amount (car coins)) coins)
                 (change amount (cdr coins))))))

推广

这个思路也可以放到另外一个子集问题上，找到集合（无重复元素，即SET）的所有子集。很容易得到：

SET的所有子集 等于 SET[1:]的所有子集 加上 SET[1:]的所有子集每个都加上SET[0]

f(set) = f(set[1:]) + map(f(set[1:]),x -> [..x,set[0]])

fun f(l: List<Any>): List<List<Any>> = l.getOrNull(0)?.let { first ->
   val subsets = f(l.subList(1, l.size))
   subsets + subsets.map { it + first }
} ?: listOf(emptyList())