确定将一定数量的钱比如100，换成1，2，5，10，20，50元的组合问题（3）

在第2个的基础上稍微优化了点，减少了递归次数

package test;

public class CoinToSum3 {
	private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };

	private static int count = 0;

	public static void main(String[] args) throws Exception {
		System.out.println(System.currentTimeMillis());
		calc(100, 5, "");
		System.out.println("totally " + count + " solutions. ");
		System.out.println(System.currentTimeMillis());// 50ms
	}

	private static void calc(int sum, int coinIdex, String pre) {
		if (sum <= 0) {
			if (sum == 0) {
				count++;
			}
		}
		for (int i = coinIdex; i >= 0; i--) {
			if (sum >= 0) {
				calc(sum - COINS[i], i, pre + " " + COINS[i]);
			}
		}
	}
}

这个消耗时间大概在50ms,比第2个在性能上提升了近1倍，不过二者的原理是一样的。