377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

 

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

Input: nums = [9], target = 3
Output: 0

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

 

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation do we need to add to the question to allow negative numbers?

Solution:

We will start with brute force. We will use recursion and we will iterate in the nums array and will check whether we can add this element or not. If yes we will decrease the target and then recall the function with the decreased target. See the code below.

Optimizing this we will just use a dp array where dp[i] will store the number of combinations for target=i. If we have already calculated for i then we don't need to calculate it again.

Now instead of using a helper function, we can do it in a for a loop.

Now we can optimize the third approach by sorting the nums array and if the current element exceeds the target we can simply stop the for loop.