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.

Constraints:

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

Let $OPT(t)$ be the number of possible combinations that add up to $t$, from the array of integers $A$. Then:

Top-Down

def combinationSum4(nums: List[int], target: int) -> int:
	solutions = {}
	
	def countCombinations(nums: List[int], t: int) -> int:
		if t in solutions: return solutions[t]
		
		if t < 0:
			solutions[t] = 0
		elif t == 0:
			solutions[t] = 1
		else:
			solutions[t] = sum(countCombinations(nums, t - num) 
							   for num in nums)
		
		return solutions[t]
	
	return countCombinations(nums, target)
	

Bottom-Up

def combinationSum4(nums: List[int], target: int) -> int:
	solutions = {}
	
	for i in range(target + 1):
		solutions[i] = 0
		for num in nums:
			if num == i:
				solutions[i] += 1
			if i - num in solutions:
				solutions[i] += solutions[i - num]
	
	return solutions[target]

Time Complexity

Let $t$ be the target number and $n$ be the number of integers in nums. There are $t$ iterations in the outer loop. Each iteration takes $\mathcal{O}(n)$ time, since the inner loop has $n$ iterations each with constant time. Therefore the total time complexity is in $\mathcal{O}(n \cdot t)$.

Space Complexity

Since the solutions for every number smaller than $t$ must be memoised, the total space complexity is $\mathcal{O}(t)$.