Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
The description was taken from https://leetcode.com/problems/combination-sum-iv/.
#O(N*T) Time, O(T) Space where T is Target and N is input Arrayclass Solution: def combinationSum4(self, nums: List[int], target: int) -> int: nums.sort() dp = [1] + [0] * (target) for i in range(1, target + 1): for num in nums: if num > i: break dp[i] += dp[i - num] return dp[-1]If we are given two inputs and we are asked to find if those two inputs can be correlated, what the minimum amount of iterations it takes for one to be the other, or what amount of one exists in the other, things like that, typically that is an indication that Dynamic Programming can be applied.
This version of the problem only requires us to return a number.
That makes it somewhat easier than returning the actual combinations as we did for the previous Combination Sum problems. Since we don't have to return the actual combinations, we can use Dynamic Programming to solve this problem instead of the previous backtracking approaches.
More specifically, we can build an array that we will use as a lookup table. We will split the problem into subproblems where each index of the table gives us how many combinations we had for that target value. Within each subproblem, we will be asking "what was the answer to this previous subproblem?" meaning, "how many combinations did we have up until this previous point?".
We will increment our current subproblem by the answer to a previous subproblem, we will expand our target by one and then repeat.
We'll start off by sorting our input array.
This is the same optimization that we used in the previous versions of this problem to nip bad paths in the bud and avoid calculating answers to subproblems that won't end up in the final result.
nums.sort()
We will then create our dp array that will hold the answers for each Combination Sum subproblem that we will refer to.
The base case of dp[0] will be if we received a target value of zero, and this case would be one because we would only have one combination for that, it would be zero.
dp = [1] + [0] * (target)
Next, we'll create our "expansion" loop, with the iterator i and this loop will traverse up to the target amount. This is the loop that we will use to expand the range of each subproblem.
for i in range(1, target + 1):
After, we will create our "subproblem partition" loop that will introduce each value from the input array into each combination.
This loop will help us calculate the subproblem of "how many combinations do we have for this number?", we will refer to previous answers to the same subproblem within our dp array and we will use these to come up with the current subproblem solution.
for num in nums:
Here we will apply the optimization that we can gain from sorting the array first.
If the number we're currently at is greater than i then that means that we haven't filled our dp lookup table up until that point yet and we won't have an answer that we can increment to our subproblem by besides zero, so we will break from the loop.
We could also get an index out of bounds error if we tried to increment by a negative index greater than the size of our array and we didn't sort the array beforehand.
if num > i: break
Otherwise, we will use the answers to previous subproblems to get our current answer.
dp[i] += dp[i - num]
Let's take the input for example, where nums is [1,2,3,4] and target is five.
We will first ask "how many combinations do we have in our table if we were to introduce the value of one within each combo that we are able to sum to one?"
The answer to that subproblem for each index that is smaller than one would be, "well, I have how many combinations we wrote for dp[i-num], plus how many combinations I already have".
We will mark that answer at the current index so that our future selves know how many combinations we had up until that point.
After that, we would ask "how many combinations do we have in our table if we were to utilize the value of two within each combo that we are able to sum to two?"
This would continue and then the final question would be "how many combinations do we have in our table if we were to utilize the value of four within each combo that we are able to sum to five?"
The answer to the final subproblem would be in the last index of the dp array, so we will return what the answer was.
return dp[-1]