[LeetCode][377. Combination Sum IV] 2 Approaches: Backtrack and DP with Follow Up Analysis

By Long Luo

This article is the solution 2 Approaches: Backtrack and DP with Follow Up Analysis of Problem 377. Combination Sum IV.

Here shows 2 Approaches to slove this problem: Backtrack and Dynamic Programming.

Backtrack

TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
int total = 0;

public int combinationSum4(int[] nums, int target) {
total = 0;
Arrays.sort(nums);
backtrack(nums, target);
return total;
}

private void backtrack(int[] nums, int remain) {
if (remain == 0) {
total++;
return;
}

for (int i = 0; i < nums.length; i++) {
if (nums[i] > remain) {
break;
}

backtrack(nums, remain - nums[i]);
}
}
}

Analysis

Time Complexity: O(nSum(target))O(n^Sum(target))
Space Complexity: O(target)O(target)

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int x : nums) {
if (x > i) {
continue;
}

dp[i] += dp[i - x];
}
}

return dp[target];
}

Analysis

Time Complexity: O(targetn)O(target * n)
Space Complexity: O(target)O(target)

Follow Up

If the given array contains negative numbers, it will result in an infinite-length permutation.

For example, if the array nums\textit{nums} contains positive integers AA and negative integers BB (where A>0A>0, B<0B<0), so there is A×B+A×(B)=0A \times B + A \times (-B)=0. Which means for any permutation whose sum of elements is equal to target\textit{target}, we can add target+A×B+A×(B)=target\textit{target} + A \times B + A \times (-B)=\textit{target}.

Therefore, as long as there is an arrangement whose sum of elements is equal to target\textit{target}, an arrangement of infinite length can be constructed.

If negative numbers are allowed, the maximum length of permutations must be limited to avoid infinite-length permutations before the number of permutations can be counted.


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗