简易货币问题条件满足提前中止

李恒道

arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，
认为值相同的货币没有任何不同，
返回组成aim的方法数
例如：arr = {1,2,1,1,2,1,2}，aim = 4
方法：1+1+1+1、1+1+2、2+2
一共就3种方法，所以返回3

如果满足条件提前终止不会导致出错
简易对数器及代码如下

function process1(arr, index, rest) {
  if (rest < 0) {
    return 0;
  }
  if (index == arr.length) {
    return rest == 0 ? 1 : 0;
  } else {
    return (
      process1(arr, index + 1, rest) +
      process1(arr, index + 1, rest - arr[index])
    );
  }
}
function process2(arr, index, rest) {
  if (rest < 0) {
    return 0;
  }
  if (rest == 0) {
    return 1;
  }
  if (index == arr.length) {
    return 0;
  }
  return (
    process2(arr, index + 1, rest) + process2(arr, index + 1, rest - arr[index])
  );
}
function randomTest() {
  for (let index = 0; index < 10000; index++) {
    const target = parseInt(Math.random() * 100);
    const arr = [1, 3, 5, 7, 9, 10, 20, 30, 50, 70, 100];
    if (process1(arr, 0, target) !== process2(arr, 0, target)) {
      console.log("err");
      break;
    }
  }
}
randomTest();