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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
 * Calculate the number of possible combinations that add up to target.
 * Dynamic Programming (Bottom-Up) approach.
 *
 * @param {number[]} nums - Array of distinct integers
 * @param {number} target - Target sum
 * @return {number} - Number of possible combinations
 */
function combinationSum4(nums, target) {
  // Initialize DP array
  const dp = Array(target + 1).fill(0);
 
  // Base case: there is one way to form the sum 0 (by not selecting any number)
  dp[0] = 1;
 
  // Fill DP array
  for (let i = 1; i <= target; i++) {
    for (const num of nums) {
      if (i >= num) {
        dp[i] += dp[i - num];
      }
    }
  }
 
  return dp[target];
}
 
/**
 * Calculate the number of possible combinations that add up to target.
 * Dynamic Programming (Top-Down with Memoization) approach.
 *
 * @param {number[]} nums - Array of distinct integers
 * @param {number} target - Target sum
 * @return {number} - Number of possible combinations
 */
function combinationSum4TopDown(nums, target) {
  // Initialize memo array
  const memo = new Map();
 
  // Define recursive function
  function combinationSum4Recursive(remainingTarget) {
    // Base case: there is one way to form the sum 0 (by not selecting any number)
    if (remainingTarget === 0) {
      return 1;
    }
 
    // Base case: there is no way to form a negative sum
    if (remainingTarget < 0) {
      return 0;
    }
 
    // If we've already computed this subproblem, return the cached result
    if (memo.has(remainingTarget)) {
      return memo.get(remainingTarget);
    }
 
    let count = 0;
    for (const num of nums) {
      count += combinationSum4Recursive(remainingTarget - num);
    }
 
    // Cache the result
    memo.set(remainingTarget, count);
    return count;
  }
 
  return combinationSum4Recursive(target);
}
 
/**
 * Calculate the number of possible combinations that add up to target.
 * Dynamic Programming with Handling Negative Numbers approach.
 *
 * @param {number[]} nums - Array of integers (can include negative numbers)
 * @param {number} target - Target sum
 * @return {number} - Number of possible combinations
 */
function combinationSum4WithNegatives(nums, target) {
  // Initialize memo array
  const memo = new Map();
 
  // Define recursive function
  function combinationSum4Recursive(remainingTarget, maxLength) {
    // Base case: there is one way to form the sum 0 (by not selecting any number)
    if (remainingTarget === 0) {
      return 1;
    }
 
    // Base case: there is no way to form a sum if we've used all allowed numbers
    // or if the remaining target is negative
    if (remainingTarget < 0 || maxLength === 0) {
      return 0;
    }
 
    // Create a unique key for the memo map
    const key = `${remainingTarget},${maxLength}`;
 
    // If we've already computed this subproblem, return the cached result
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    let count = 0;
    for (const num of nums) {
      count += combinationSum4Recursive(remainingTarget - num, maxLength - 1);
    }
 
    // Cache the result
    memo.set(key, count);
    return count;
  }
 
  // We can't use more than target numbers if all numbers are at least 1
  // If there are negative numbers, we need to set a reasonable limit
  const maxLength = target;
 
  return combinationSum4Recursive(target, maxLength);
}
 
// Test cases
console.log(combinationSum4([1, 2, 3], 4));  // 7
console.log(combinationSum4([9], 3));  // 0
console.log(combinationSum4([1, 2, 3], 32));  // 181997601
 
console.log(combinationSum4TopDown([1, 2, 3], 4));  // 7
console.log(combinationSum4TopDown([9], 3));  // 0
console.log(combinationSum4TopDown([1, 2, 3], 32));  // 181997601
 
// This would cause an infinite loop without the maxLength parameter
// console.log(combinationSum4WithNegatives([1, -1], 1));  // Depends on maxLength
console.log(combinationSum4WithNegatives([1, 2, 3], 4));  // 7