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).
1import java.util.Arrays;
2
3public class Solution {
4 public int combinationSum4(int[] nums, int target) {
5 int[] memo = new int[target + 1];
6 Arrays.fill(memo, -1);
7 memo[0] = 1;
8 return dfs(nums, target, memo);
9 }
10
11 private int dfs(int[] nums, int target, int[] memo) {
12 if (target < 0) return 0;
13 if (memo[target] != -1) return memo[target];
14
15 int count = 0;
16 for (int num : nums) {
17 count += dfs(nums, target - num, memo);
18 }
19
20 memo[target] = count;
21 return count;
22 }
23
24 public static void main(String[] args) {
25 Solution sol = new Solution();
26 int[] nums = {1, 2, 3};
27 int target = 4;
28 System.out.println(sol.combinationSum4(nums, target));
29 }
30}The Java solution leverages a recursive function with an integer array, 'memo', to store the number of ways to sum to each target value. The solution uses Depth First Search (DFS) combined with memoization.
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).
1#
This C implementation uses a DP array where each element at index i stores the number of ways to form the sum i, iterating through each number in nums to update the array.