Teaching Kids Programming – Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The answer is guaranteed to 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?

Thinking of this problem as: Given a knapsack with capacity T, and a list of items with their weights. Find out the number of possible combination that to pick the items into the knapsack i.e. sum of chosen items is T.

Bruteforce and BackTracking Algorithm to Pick the Numbers

For each item, we can choose pick (if it is less than the T or we have capacity to pack this) or pick next one. Once there is no remaining capacity in the knapsack, we increment the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        ans = 0
        
        def pick(left, T):
            nonlocal ans
            if T == 0:
                ans += 1
                return
            for i in range(len(nums)):
                if T >= nums[i]:
                    pick(i, T - nums[i])
                
        pick(0, target)
        return ans

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        ans = 0
        
        def pick(left, T):
            nonlocal ans
            if T == 0:
                ans += 1
                return
            for i in range(len(nums)):
                if T >= nums[i]:
                    pick(i, T - nums[i])
                
        pick(0, target)
        return ans

One optimisation is to sort the items in the ascending order – and backtrack once the item is exceeding the current capacity. However, this is still too slow – as there are exponential combinations of choosing the items.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        ans = 0
        
        nums.sort()
        def pick(left, T):
            nonlocal ans
            if T == 0:
                ans += 1
                return
            for i in range(len(nums)):
                if T >= nums[i]:
                    pick(i, T - nums[i])
                else:
                    break
                
        pick(0, target)
        return ans

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        ans = 0
        
        nums.sort()
        def pick(left, T):
            nonlocal ans
            if T == 0:
                ans += 1
                return
            for i in range(len(nums)):
                if T >= nums[i]:
                    pick(i, T - nums[i])
                else:
                    break
                
        pick(0, target)
        return ans

Bottom Up Dynamic Programming Algorithm of Solving Knapsack Problem

Let be the number of ways to pick items to capacity T, then it is sum of where i is the items. This is actually similar to climbing stairs problem.

With Bottom-up DP, we calculate the f(0), f(1), f(2) and up to f(T). and we store the numbers in an O(T) array so that we can re-use the values without needing to calculate them.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for j in nums:
                if i >= j:
                    dp[i] += dp[i - j]
        return dp[-1]

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for j in nums:
                if i >= j:
                    dp[i] += dp[i - j]
        return dp[-1]

The time complexity is O(T.N) where N is the number of the items. And space complexity is O(T) as we need an array with size T – to calculate the value F(0), F(1) .. to F(T).

Top Down Dynamic Programming Algorithm to Compute the Combination Sum of Target

As soon as we have the Dynamic Programming Transistion Function and the terminal conditions, we can implement DP in a straightforward Recursive manner. However, we need to use the @cache or @lru_cache(None) to apply the memoization technique so that only the F(0) to F(T) values are calculated once.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 1
            if n < 0:
                return 0
            ans = 0
            for i in nums:
                ans += f(n - i)
            return ans
        return f(target)

class Solution:
    def combinationSumToTarget(self, nums: List[int], target: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 1
            if n < 0:
                return 0
            ans = 0
            for i in nums:
                ans += f(n - i)
            return ans
        return f(target)

Time complexity is O(NT) and space complexity is O(T) – same as the Bottom-up Dynamic Programming Algorithm.

See also: Using BackTracking Algorithm to Find the Combination Integer Sum

Another similar problem of unbounded knapsack problem via Dynamic Programming Algorithms: Teaching Kids Programming – Dynamic Programming Algorithm to Compute Minimum Number of Coins

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —