数组组合 算法题

[wss534857356]

// 类似这种
［1，2，5，10，20，50，100］，可以从里面取若干个数，要求得出和为100的不同取法有多少？
解题思路就是递归调用, 同时防止数据重复, 类似乘法中的25=52的情况
比如1, 2, 3 三个分支, 递归三次 1只调用 1, 2, 3分支, 2只调用2, 3分支, 3只调用3自己
递归的数组应该为:
[1,1,1],
[1,1,2],
[1,2,2],
[1,2,3],
[1,3,3],
[2,2,2],
[2,2,3],
[2,3,3],
[3,3,3],

以下是js的解决方案

(function() {
    var s = 0;
    var arr = [1, 2, 5, 10, 20, 50, 100];
    function sum(n, k) {
      s++;
      var num =0;
      if(n === 0) return 1;
      if(n < 0)return 0;
      for(let i = k||0 ; i< arr.length; i++) {
        num += sum(n-arr[i], i);
      }
      return num;
    }
    console.log(sum(100));
    console.log(s);
  }())