377/main.js


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#!/home/devi/.bun/bin/bun

var combinationSum4 = function (nums, target, memo = {}) {
  let sum = 0;
  if (target in memo) {
    return sum + memo[target];
  }
  if (target === 0) {
    sum++;
    return sum;
  }
  if (target < 0) {
    return sum;
  }

  for (let num of nums) {
    var remainder = target - num;
    if (remainder === 0) {
      sum++;
      if (remainder in memo) {
        memo[remainder]++;
      } else {
        memo[remainder] = 1;
      }
    }
    if (remainder > 0) {
      memo[remainder] = combinationSum4(nums, remainder, memo);
      sum += memo[remainder];
    }
  }

  console.log(memo);
  memo[target] = sum;
  return sum;
};

console.log(combinationSum4([1, 2, 3], 4));
console.log(combinationSum4([4, 2, 1], 32));