Swift Leetcode Series :Combination Sum IV

Backtracking + DP = Beautiful brain workout

Varun
Varun
Apr 19 · 4 min read
Leetcode 377 (Medium)

You can also read the full story on The Swift Nerd blog with the link above.

This is a very a variant of classical coint change problem and really important to solve it yourself if you want to improve your recursion and Dynamic programming.

Problem Description

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:

Example 2:

Constraints

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

Solution

The problem is similar to the classical problem of Coin change problem. We can think about breaking the problems into sub problems recursively and then build our solution.

Backtracking

Whenever you hear the word “combinations” or “permutations”, ideally the word backtracking should come to your mind. We can use backtracking to permute all possible combinations of the numbers and choose the branches which suit our condition. Take a look at the example from coin change problem.

We can start from the target and recursively try every combinations of the numbers from the nums array. If we have a target T and take a number A[i] from Array where 0 <= i < n, then the sub problem would become to find total combinations for T — A[i] which would in turn recursively permute all possible paths. As soon the the T — A[i] == 0, this means that the current branch is a solution and we can add it to the result. If T — A[i] < 0, this means that the current permutations of the numbers can not give us the target sum hence we can discard that branch.

Important:

When you would try to run the problem, it would run for the sample test cases but you would get TLE(Time limit exceeded) on submit. Why? Because of the recursion depth. For a backtracking approach, the complexity would be of exponential order O(NM). Where N is the size of the array and M is final sum. In the constraints, max size of the array is size as 200 and target can be 1000. So we are talking about operations of the order 200 1000 which is massive (don’t forget the recursion stack for space). But since we are repeating a lot of operations, we can cache them and this is where Dynamic programming comes into picture.

Since we are not able to submit the problem without DP, then it is the only possible solution (DP) but backtracking approach is important to develop intuition and understanding of the sub problems. With less constraints, we backtracking solution can also get accepted.

Dynamic Programming

This is a classical dynamic programming problem because the problem can be broken down into sub problems and optimising the local result would help to optimise the global result. (Overlapping subproblems and Optimal structure). The code is going to be more or less same, but we are going to cache the result of solving every sub problem. DP[i] would denote the total number of possible combinations for achieving the sum i. We would be using top down Dynamic programming as we would be starting from our main problem and work towards the smaller sub-problem. There is bottom-up approach as well, where we would start solving sub problems from 1 and work towards the main problem and the process we would have solved all the possible recursion steps which we would need to solve the final problem.

Top-Down Approach

Our DP array (dp) will contain cells (dp[i]) where i will represent the remaining space left before T and dp[i] will represent the number of ways the solution (dp[T]) can be reached from i.

At each value of i as we build out dp we’ll iterate through the different nums in our number array (N) and consider the cell that can be reached with each num (dp[i-num]). The value of dp[i] will therefore be the sum of the results of each of those possible moves.

Code

Backtracking (Recursion)

Code: Top-Down Approach (DP)

Complexity Analysis

Backtracking

Time = O(NM) where N is the size of the array and M is the total amount.

Space = O(1)

Think of recursion as a tree where each path represents a way to make up the amount and the height of the tree is the combination that has the most coins. Since the amount is fixed, the combination containing the most coins would be using the smallest coin. In the worst case, the tree’s root node can have n child nodes. Therefore, the runtime becomes exponential.

Dynamic Programming

Time = O(N * M) where N is the size of the array and M is the total amount.

Space = O(M) (For storing the results from 0 to M )

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github

Nerd For Tech

From Confusion to Clarification

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Varun

Written by

Varun

Senior iOS Engineer. Writer at https://theswiftnerd.com

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.