判断数组组合

[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加一. 然后就是不知道该怎样实现这个排列组合. 最后以失败告终. 丧...