Blind 75.21 - Combination Sum

Combination sum.

Problem description

Taken directly from LeetCode.

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 we need to add to the question to allow negative numbers?

Solution type

Caching via DP.

Solution

Caught this one pretty quickly - the base case is simply that there is one way to sum to 0 (don’t use any numbers from nums). From there, the recursive relation is for any target value \(n\), \(\textrm{CS}(n) = \sum_{x \in \texttt{nums}} \textrm{CS}(n -x)\). In plain English, take the sum of the number of ways to get to \(n - x\) for all \(x \in \texttt{nums}\) and that’s the number of ways to get \(n\). Memoize to avoid exponential time complexity.

You can build up from 1 up to target like this and for a neat \(O(nt)\) solution, where \(n\) is the size of nums and \(t\) is the value of target.

def combinationSum4(self, nums: List[int], target: int) -> int:
    memo = [0 for _ in range(target + 1)]
    memo[0] = 1 # there is 1 way to get 0: don't use any numbers in nums
    for i in range(1, target + 1):
        numWays = 0
        for num in nums:
            numWays += memo[i - num] if i - num >= 0 else 0
        memo[i] = numWays
    return memo[target]

For some reason the top-down approach was way slower? As in it timed out on the larger test cases. I’ve checked with other solutions as well and I think that this is a correct Python implementation…the constant factors are definitely higher, and there’s this additional dependency introduced on the numbers in nums – smaller numbers will require more checks in memo, which I can see becoming a nontrivial timesink. Class functions are slow and I think using Python doesn’t help.

def getNumWays(self, memo: List[int], nums: List[int], target: int) -> int:
    numWays = 0
    if memo[target]:
        numWays = memo[target]
    else:
        for num in nums:
            numWays += self.getNumWays(memo, nums, target - num) if target - num >= 0 else 0
        memo[target] = numWays
    return numWays

def combinationSum4(self, nums: List[int], target: int) -> int:
    memo = [0 for _ in range(target + 1)]
    memo[0] = 1 # there is 1 way to get 0: don't use any numbers in nums
    return self.getNumWays(memo, nums, target)

Bottom-up DP works fine though, so there’s no reason to fret.