I have recently came across a problem where I need to solve the subset sum problem. In this problem we have an array of numbers and we need to find the elements from the array whose sum matches a given number. You can find more details of the subset sum problem in the Wikipedia page here.
We can solve this problem with the help of recursion. It will help us solve it with less complexity of the multiple nested loops.
For the simplicity of the understanding we will use the array
[50, 40, 30, 20] and will try to find the
sum=100 from the array.
So, we will start with the very first element in the array. We have 2 choices here. Either select that element or reject. Now let’s explore the possibilities in the both the options.
1. Select an element: If we select that element, then we will include that in the result list and we need to find the remaining sum from the list excluding the first element.
So, if we select
50, we need to find the remaining sum (i.e.
100-50: 50) from the array excluding first element (i.e.
[40, 30, 20])
2. Reject an element: If we don’t select the element, then we will not include it in the result list and we need to find the sum exactly the same from the remaining list after excluding the element we rejected.
So, it we don’t select
50, we need to find the same sum (i.e.
100) from the array excluding first element. (i.e.
[40, 30, 20])
This causes 2 types of possibilities in each step of the recursion. Select or Reject the first element. This will cause a binary tree with the possibilities like this:
In each path at the end, all the selected elements in that path will be the answer to our problem.
Now, let’s talk about how and where do we end in this recursion loop.
###Breaking or Ending the recursion:
Before deciding the path of selecting or rejecting first element, check if the requested
0 or not. If
sum=0, then we have found our way and break it. Else we have still need to go and continue.
One other check we can make is if we exceeded the value required for the
sum. Whenever we select an element we subtract that value from the sum and pass it forward. So, if the sum is less than
0, then there is no point of going forward, and break the loop. This will improve the performance.
At last, if we reached to the end and still
sum != 0, then we can break as this path failed to find a solution.
So, this 3 checks will help us break the loop in case where we find a solution, or there won’t be a solution going forward.
The following function is a
Java function and will return the path in the result variable. It is simple to understand.
Whenever we select an element we add it to the result. We remove it, if that path fails to find a solution with that element selected and goes with rejecting that element.
This will return the very first path it finds, which solves our problem.
The following diagram shows set of variables passed as we reach go in each recursion:
The values for the middle nodes is not included because of the space issues.
So, here we got the result:
Try to play with the different arrays for input set to get the different outputs.
If we provide the array in ascending or descending order, it will ensure we get the same result every time. Because there can be more than 1 solution for the given array. But, putting it in order will provide the same result providing the same set.