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).
1#include <vector>
2#include <iostream>
3
4class Solution {
5public:
6 int combinationSum4(std::vector<int>& nums, int target) {
7 std::vector<int> dp(target + 1, -1);
8 dp[0] = 1;
9 return helper(nums, target, dp);
10 }
11
12private:
13 int helper(const std::vector<int>& nums, int target, std::vector<int>& dp) {
14 if (target < 0) return 0;
15 if (dp[target] != -1) return dp[target];
16
17 int res = 0;
18 for (int num : nums) {
19 res += helper(nums, target - num, dp);
20 }
21
22 dp[target] = res;
23 return res;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<int> nums = {1, 2, 3};
30 int target = 4;
31 std::cout << sol.combinationSum4(nums, target) << std::endl;
32 return 0;
33}The C++ solution uses a helper function for recursion and memoization to count combinations that add to the target. It initializes a DP array with -1 and handles subproblem results to find the total combinations.
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).
1using System;
public class Solution {
public int CombinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
foreach (int num in nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
public static void Main(string[] args) {
var sol = new Solution();
Console.WriteLine(sol.CombinationSum4(new[] { 1, 2, 3 }, 4));
}
}This C# solution uses a DP array approach to calculate the number of combinations iteratively by determining how many ways each sub-target can be formed from the elements in nums.