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

常用的递归解法

package test;

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

	private static final int SUM = 100;

	private static int cnt = 0;

	public static void main(String[] args) {
		System.out.println(System.currentTimeMillis());
		calc(0, 0, "");
		System.out.println("total " + cnt + " solutions. ");
		System.out.println(System.currentTimeMillis());// 110 ms
	}

	private static void calc(int sum, int coinIndex, String pre) {
		if (SUM == sum) {
			++cnt;
		}

		for (int i = coinIndex; i < COINS.length; i++) {
			if (SUM - sum >= 0) {
				calc(sum + COINS[i], i, pre + " " + COINS[i]);
			}
		}
	}
}

这个消耗时间大概在110ms,比第1个逊色多了。。。而且代码晦涩难懂、不好理解