Approach 1: Recursion + Memoization [top-down]
Notice that the array does not contain any duplicates and we can use a number as many times as we want. It is easy to identify that this problem can be solved using recursion by considering every number and then recursing to find the remaining sum.
// this will give TLE!
public int combinationSum4(int[] nums, int target) {
if (target == 0) {
return 1;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += combinationSum4(nums, target - nums[i]);
}
}
return res;
}
If we draw a part of recursion tree, it is easy to identify that there are overlapping subproblems:
nums = [1, 3, 2]
target = 4
4
/ | \
3 1 2
/|\ | /\
2 0 1 0 1 0
This calls for memoization! Each state is defined only by the “target” so all we need to do is memoize the number of ways to achieve each target.
// dp[i] = number of ways to achieve target i
private int[] dp;
public int combinationSum4(int[] nums, int target) {
dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(nums, target);
}
private int helper(int[] nums, int target) {
if (dp[target] != -1) {
return dp[target];
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += helper(nums, target - nums[i]);
}
}
dp[target] = res;
return res;
}
Approach 2: Dynamic Programming [bottom-up]
If we are guaranteed that the numbers in the input array are in ascending order, it is easy to identify a bottom-up solution as well. Define dp[i] as number of ways to achieve target i (dp[0] = 1). Let the input array be nums = [a_1, a_2, …, a_n] where a_1<a_2<..<a_n. Clearly, we cannot achieve a target between 0 and a_1 (as a_1 is the smallest number in the input array). So dp[0..a_1=1] = 0. Now, assuming we have solution for dp[0…i-1], to achieve any target dp[i] all we have to do is add all dp[i-nums[j]] where i-nums[j]>=0. Consider input [1,2,3], to achieve target 6, the last number can be 1 or 2 or 3. So dp[5] = dp[5-1] + dp[5-2] + dp[5-3].
Note: The DP approach is similar to LC 322. Coin Change
int combinationSum4(vector<int>& nums, int target) {
// sanity check
if (nums.size()==0)
return 0;
sort(nums.begin(), nums.end());
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int i=nums[0]; i<=target; i++)
for (int j=0; j<nums.size() && nums[j]<=i; j++)
dp[i] = ((long int)dp[i]+dp[i-nums[j]])%2147483647; // to prevent overflow
return dp[target];
}
Or we could do it without sorting in this way:
// Java solution so overflow like in C++ not taken into account
public int combinationSum4(int[] nums, int target) {
int[] comb = new int[target + 1];
comb[0] = 1;
for (int i = 1; i < comb.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
}