DP — Combinatorics Problem using Memoization

As discussed in the previous blog, the three most common types of DP problems are - 1. decision problem, 2. combinatorics problem, and 3. optimization problem. This time around, we’re going to see about solving combinatorics problems using DP.

What is a combinatorics problem?

Combinatorics is all about the number of ways of choosing some objects out of a collection and/or the number of ways of their arrangement. For example, how many ways can 10 be obtained using an array of numbers consisting of {2,3,5,10}? The answer to that is two: {2,3,5} and {10}.

Note

If you’re new to DP or need a quick check on some basic terminologies concepts especially on memoization, check out my blog over here or any other resources, as moving on with the concepts requires some familiarity with the basics of DP. The problem which I have chosen to go with is an expansion of the very same problem which I have discussed in my last blog as a decision problem.

DP — Decision Problem using Memoization

Now, let’s take an example of a combinatorics problem and try to solve it. Given an array of distinct integers candidates and a target sum, return a possible combination of candidates where the chosen numbers sum to target. Given that,

1. the same number may be chosen from candidates any number of times
2. the target sum and numbers in the array are all positive integers.

Well, if you remember about the decision problem, this is just an expansion of the very same problem. In the decision problem, we have to find whether the given target sum was possible using the elements from the given array. Over here, we have to come up with a possible combination if the target sum is achievable.

So, the basic brute recursive algorithm will be as the following:

1. We can take a number from the array and subtract it from the target sum. Now, we recursively call the function with the new target sum.
2. The base can be made to check whether the target sum is equal to zero(the target sum is achievable) or less than zero(the target sum is not achievable).
3. If the sum is equal to zero, we return an empty list where we’ll be adding the elements used to get there, during the return of each recursive call.
4. Else, we return null.

pictorial depiction of the brute force algorithm

I hope we have got a decent intuition on how the algorithms works, so without further ado let’s check out the code:

Well, this solution just works fine for a small test case like the one shown in the code. But, the time complexity of the algorithm is O(m*nᵐ), where n is the size of the array and m is the target sum.

But by taking the brute force approach, we have come to an observation of the underlying DP’s characteristics in this problem. Which are the optimal substructure property and overlapping subproblems. As you could recall from the algorithm, we subtract the original target sum with a number from the array and ask the original question but with a new target sum — which is nothing but the optimal substructure property. The overlapping subproblems can be easily observed when you trace out the recursion tree:

overlapping subproblems

So, we’re familiar with these kinds of cases, and the obvious solution that comes to our mind is memoization. Our goal is to cut down the repeated recursive calls with the same parameters. So, we introduce a memo object(can be a hashmap, array, dictionary based on your language preference) into our brute algorithm, to keep track of the previously visited subproblems in order to avoid repeated recursive calls.

the brute force algorithm

So, we add another base case condition to check whether the target sum is present in the memo object(can be a hashmap, array, dictionary based on your language preference). If it is present in the memo object, we return the result for the particular target sum which was stored as a key-value pair in the memo object.

Now, this code is fairly efficient as the time complexity of this code is O(n*m²). I would like for you all, to try to sketch out the recursion tree for the memoized code, to understand how memoization helps in the huge cut down in time complexity of the algorithm.

Quick Recap

1. We saw about ‘What is a combinatorics problem?’ and an example problem to go with it.
2. We laid out a brute force algorithm to solve the problem.
3. We observed the characteristics of DP in our brute force algorithm.
4. Then, we memoized the code, to make the brute force algorithm much more efficient.

What’s next?

I would like you all to try out 2 problems which are extensions of the very same problem we have taken. Can you return all the possible combinations of the solutions to the problem? You could check out the problem over in leetcode(although a backtracking solution would be much efficient and intuitive in this case):

https://leetcode.com/problems/combination-sum/

The other version is to find the best possible combination(one with the minimum number of elements) among all possible solutions.

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post with an optimization problem and how to solve the same using DP.

References

1. https://www.hackerearth.com/practice/math/combinatorics/basics-of-combinatorics/tutorial/
2. https://www.youtube.com/watch?v=oBt53YbR9Kk&t=6582s