判断数组组合

[nunnly]

Write a function that counts how many different ways you can make change for an amount of money, given an array of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2:

1+1+1+1, 1+1+2, 2+2.
The order of coins does not matter:
1+1+2 == 2+1+1
Also, assume that you have an infinite ammount of coins.

Your function should take an amount to change and an array of unique denominations for the coins:

 countChange(4, [1,2]) // => 3
 countChange(10, [5,2,3]) // => 4
 countChange(11, [5,7]) // => 0

[Caocp]

function countChange(money, obj){
 var len = obj.length;
 var num = 0;
 if(len == 2){
 var num1 = obj[0];
 var num2 = obj[1];
 for (var i = 0; i <= money; i++) {
 for (var j = 0; j <= money; j++) {
 if(money == i*num1 + j*num2){
 num++;
 }
 }
 }
 }else if(len == 3){
 var num1 = obj[0];
 var num2 = obj[1];
 var num3 = obj[2];
 for (var i = 0; i <= money; i++) {
 for (var j = 0; j <= money; j++) {
 for (var k = 0; k <= money; k++) {
 if(money == i*num1 + j*num2 + k*num3){
 num++;
 }
 }
 }
 }
 }
 console.log(num);
 }

[nunnly]

这是一个经典的分硬币的问题，基础算法

function countChange(money, coins) {
 if(money < 0 || coins.length === 0){
 return 0
 }else if(money === 0){
 return 1
 }else {
 return countChange(money - coins[0], coins) + countChange(money, coins.slice(1))
 }
}

[muzishuiji]

天哪,做了大半天,没做出来.我本来的想法是
就是总数除以每个面值取整,就是这个面值的最大个数,然后每个面值的对应数组就是0到最大个数的数值构成的数组,然后把这些数组存下来,对这些数组进行相加的排列组合,判断得到的和,等于总数就把count加一.
然后就是不知道该怎样实现这个排列组合.
最后以失败告终.
丧...