6.1.4 Recursion Example: Make Sum

In this example, you are going to explore a few more complicated recursion concepts.

The problem you are trying to solve is to determine if a combination of numbers can be put together to add up to a given sum.

For example, if given the numbers 4, 9, 3, 7, can you add up to 14? The answer would be yes, by using 4, 3, and 7.

With the same set of numbers, if asked to add up to 15, the answer would be no, since there is not a combination that can sum to 15.

Multiple Base Cases

When looking at this recursively, there are two base cases to consider. The first base case is a successful completion where our combination adds up to the desired output. The second base case is that you got to the end of the list without hitting the target.

if (sumSoFar == target) return true; // success
if (index == nums.size()) return false; // fail

The other thing that makes this problem interesting is that you need to consider more than one recursive call.

Determining whether there is a valid combination means that you need to look at all possible permutations. For example, in the above list, you cannot just consider the 4, then the 9 then the 3 because you would be over. The winning combination actually skips the 9.

So you should notice there are two recursive calls, one for including the next number and one for excluding the next number. By including the two calls, you end up testing all the permutations.

solveSum(nums, index+1, sumSoFar, target) // skip next number
solveSum(nums, index+1, sumSoFar+nums[index], target); // include next number

Notice as well that this function returns a boolean and that the two recursive calls are joined with an or. This means the statement will be true if any one of the permutations are successful.

makeSum vs. solveSum

You should also notice that there is a helper function for this problem. The way the recursive call works, it needs more than just the numbers list and target. It also needs to track what the current sum is and which index is next to be considered from the vector.

Since the end-user doesn’t need to know how to start the recursive call, this program uses an intermediate step that takes the basic information from the user and creates the first recursive call for solveSum method.

Explore This Example

Take some time to explore this example. This is a good example of the power of recursion. Without the comments, the recursive function is only three lines, yet it creates and tests all possible permutations in those three lines. Try creating your own makeSum calls and see if they pass or not.

Try This Example