Sponsored
Sponsored
This approach involves creating a recursive solution while storing intermediate results in a memoization array to avoid redundant calculations. Define a recursive function that calculates the number of ways to reach the target from the given list, and store the results of subproblems.
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
1var combinationSum4 = function(nums, target) {
2 const memo = Array(target + 1).fill(-1);
3 memo[0] = 1;
4
5 const dfs = (target) => {
6 if (target < 0) return 0;
7 if (memo[target] !== -1) return memo[target];
8
9 let count = 0;
10 for (const num of nums) {
11 count += dfs(target - num);
12 }
13
14 memo[target] = count;
15 return count;
16 };
17
18 return dfs(target);
19};
20
21console.log(combinationSum4([1, 2, 3], 4));The JavaScript solution makes use of memoization to handle previously solved subproblems, employing a recursive method to find multiple combinations to form the target sum.
In this method, an iterative bottom-up approach is used. A DP array is created where each index represents the number of ways to sum to that index using numbers from nums. We incrementally build solutions from smaller subproblems to solve for larger targets.
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
1public
The Java program implements a dynamic programming solution with a bottom-up approach, iterating through the target and updating the DP table with the number of ways to form each possible sum.