const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

// 尾递归优化
const factorial2 = (n, total = 1) => {
  if (n <= 1) return total
  return factorial2(n - 1, total * n)
}

function fib(n) {
  let a = 0;
  let b = 1;
  let c = a + b;
  for (let i = 3; i < n; i++) {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}

function isSequence(a, b) {
  let i = 0;
  let j = 0;

  while(i < a.length && j < b.length) {
    if (a[i] === b[j]) i++;
    j++;
  }

  return i === a.length;
}

class MinCoinChange {
  constructor(coins) {
    this.coins = coins
    this.cache = {}
  }
  makeChange(amount) {
    if (!amount) return []
    if (this.cache[amount]) return this.cache[amount]
    let min = [], newMin, newAmount
    this.coins.forEach(coin => {
      newAmount = amount - coin
      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount)
      }
      if (newAmount >= 0 && 
        (newMin.length < min.length - 1 || !min.length) && 
        (newMin.length || !newAmount)) {
        min = [coin].concat(newMin)
      }
    })
    return (this.cache[amount] = min)
  }
}
const rninCoinChange = new MinCoinChange([1, 2, 5, 10])
console.log(rninCoinChange.makeChange(120))