Swift Leetcode Series :Combination Sum IV
Combination Sum IV (Leetcode 377) -
Difficulty: Link: April Leetcoding Challenge 2021: Day 19 Given an array of distinct integers nums and a target integer…
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.
Given an array of distinct integers
nums and a target integer
target, return the number of possible combinations that add up to
The answer is guaranteed to fit in a 32-bit integer.
Input: nums = [1,2,3], target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
Note that different sequences are counted as different combinations.
Input: nums = , target = 3
1 <= nums.length <= 200
1 <= nums[i] <= 1000
- All the elements of
1 <= target <= 1000
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.
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.
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.
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.
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: Top-Down Approach (DP)
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.
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 )