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 <stdio.h>
2#include <string.h>
3
4int combinationSum4(int* nums, int numsSize, int target) {
5 int memo[target + 1];
6 memset(memo, -1, sizeof(memo));
7 memo[0] = 1; // Base case
8
9 int dfs(int remain) {
10 if (remain < 0) return 0;
11 if (memo[remain] != -1) return memo[remain];
12
13 int count = 0;
14 for (int i = 0; i < numsSize; i++) {
15 count += dfs(remain - nums[i]);
16 }
17
18 memo[remain] = count;
19 return count;
20 }
21
22 return dfs(target);
23}
24
25int main() {
26 int nums[] = {1, 2, 3};
27 int target = 4;
28 printf("%d\n", combinationSum4(nums, 3, target));
29 return 0;
30}This C solution uses a memoization technique to store results of subproblems in an array called memo. The main idea is to recursively explore all numbers in the array, and try to put each one into the combination until reaching the target.
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#include <vector>
2#include <iostream>
class Solution {
public:
int combinationSum4(std::vector<int>& nums, int target) {
std::vector<unsigned int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (const auto& num : nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
};
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 3};
int target = 4;
std::cout << sol.combinationSum4(nums, target) << std::endl;
return 0;
}In this C++ solution, we use an array dp to store computed values. For each number from 1 to the target, we explore all available nums to determine how many ways the target can be formed.