How to Use Recursion to Solve a PlusMinus Problem

amkemp
amkemp
Jun 22, 2020 · 7 min read

Today we talk about how to use recursion to solve a specific algorithm problem.

I recently did a coding challenge as part of a job interview and they asked an algorithm problem I hadn’t come across before. I thought this one was particularly interesting and at the time I had no clue how to solve it, so today let’s break it down together. Here’s the problem:

Have the function PlusMinus(num) read the num parameter being passed which will be a combination of 1 or more single digits, and determine if it's possible to separate the digits with either a plus or minus sign to get the final expression to equal zero. For example: if num is 35132 then it's possible to separate the digits the following way, 3 - 5 + 1 + 3 - 2, and this expression equals zero. Your program should return a string of the signs you used, so for this example your program should return -++-. If it's not possible to get the digit expression to equal zero, return the string not possible.If there are multiple ways to get the final expression to equal zero, choose the one that contains more minus characters. For example: if num is 26712 your program should return -+-- and not +-+-.

Ok, there’s a lot of information in this problem so let’s break it down:

I think this problem phrases it oddly but we are going to take in a number that will be one or more digits. First we need to strip the number down to the individual integers that make up the number. Then we want to figure out if it is possible to put plus signs or minus signs between the numbers in some combination to get the whole thing to equal zero. Finally we return that list of pluses and minuses or we return “not possible” if it isn’t possible for those numbers to equal zero in any combination.

After we make sure we understand the problem, the next step is to figure out some examples. There is a good one provided in the problem so let’s use that one, and I also added one that gives us our ‘not possible’ outcome:

let num = 35132
//expected output: '-++-'

let anotherNum = 199
//expected output: 'not possible'
  1. First, we need to find a way to get our input into the correct form. We are given an integer so we need to break that integer apart into its individual numbers.
  2. Let’s make an array to hold our possible solution strings
  3. We’re going to write a helper function to traverse through our array of numbers. This is where our recursion comes in.
  4. We’re going to write another helper function to figure out the best possible solution from the ones we have come up with.
  5. Then we return the possibility with the most minuses or we return ‘not possible’

I know I kind of glazed over the juicy details above, I’ll break it down below each code snippet.

function PlusMinus(num) {
let array = String(num).split('').map((num) => parseInt(num));
const possibilities = []

We need this integer to be broken down into the individual numbers that make it up so I want to split it up into an array. I can do that with the string method split but I have to make my integer a string first.

  1. Make num a string. How? I’m using it as a function to perform type conversion, you can look it up under the Constructor heading here.
  2. Use split method on the string, this will turn it into and array of strings containing the string version of each of our numbers
  3. Map over our new array of strings and turn each of them into numbers again using parseInt. If you aren’t familiar with parseInt look up the documentation.
  4. Make an array to hold our lists of possible sign combinations that we are going to make in the next step.

Now we get to the meat of this problem: how to write the recursive part of our solution. Explanation below:

const traverse = ([currNum, ...otherNums], combination, sum) => {
if (otherNums.length === 0) {
if (sum + currNum === 0) possibilities.push(combination + '+');
if (sum - currNum === 0) possibilities.push(combination + '-');
} else {
traverse(otherNums, combination + '+', sum + currNum);
traverse(otherNums, combination + '-', sum - currNum);
}
};
  1. Our function is going to take in a piece of our original array. What I’m doing on the first line is destructuring that piece of the array so that I can access the various parts of it with variables that I declare. In this case currNum now refers to the first number of that array and otherNums now refers to the rest of the numbers in that array.
  2. For our base case we check to see if there are any otherNums besides the one we named currNum. If there aren’t then that means we’re down to an array of one number and we can push the combination of “+” and “-” signs that we have built as we called these functions to our possibilities array. Why do we need the possibilities array? We need the possibilities array so that at the very end we can check to see which possible combination of signs has the most “-” signs and that will be the one we return.
  3. If we haven’t reached the point of having only one array element yet then we call our traverse function again, once for the plus possibility and once for the minus possibility. I highly recommend using a site like AlgoViz to really understand the order in which the functions are being put onto the call stack. Just copy the code from the bottom of this article into the code editor on AlgoViz and watch it run. Remember that the first function call we hit will get added to the call stack and nothing after it will run until after it is resolved.
const mostMinus = (possibilitiesArray) => {
return possibilitiesArray.reduce((acc, curr) =>
[...acc].filter((sign) => sign === '-').length >
[...curr].filter((sign) => sign === '-').length ? acc : curr );
};
  1. We pass in an array of possible sign combinations which at this point should be an array of strings containing the combination of plus signs and minus signs it took to get our results. This array got built when we reached the final step of our traverse function above when we pushed our combination to the array.
  2. We will use the reduce array method on our possibilitiesArray to reduce this array down to the possibility with the most minus signs. It will return a string. If we look at the docs for reduce we see that if we don’t pass in an initial value for the accumulator it will just use our first value in the array which is what we want for our current purpose.
  3. We spread our accumulator into an array and then filter it using the condition of the sign being a “-”. The accumulator at this point is just the first string of pluses and minuses that was in our array because we didn’t pass in an initial value to the accumulator.
  4. We spread our current element into an array and also filter it using the condition of the sign being a “-”.
  5. We compare the two to see which one is bigger, ie which on has more minus signs. We are using a ternary operator here if you aren’t familiar with it look it up it can be really useful.
  6. If the accumulator has more minus signs we return it otherwise we return the current string we are looking at. Either way our possibilities array is now reduced down to only one string, the one that contains the most minus signs.

Up until now we haven’t actually done anything to get to our solution. We’ve only written helper functions that we haven’t called. It’s time to call our functions and return our result:

    traverse(array.slice(1), '', array[0]);
return possibilities.length ?
mostMinus(possibilities) : 'not possible';
}
  1. Now we call our traverse function that we already wrote. We will pass in as the first argument a slice of our array from index one to the end. This is because we will use the first value to be our starting sum. We pass in an empty string to be our initial value for combination, and we pass in the first element of our array (the one we sliced off) as our initial value for sum.
  2. For our return statement we see if there are any strings in our possibilities array, if there are we call our mostMinus function on the array, and if not we return the string ‘not possible’ because we didn’t end up with any possible combinations of “+” or “-” to make our numbers equal zero.

There is a lot to go through in this problem but it is an interesting one to work through. It also uses a lot of really helpful array methods that you should know. If you don’t look them up and read the docs. I really recommend figuring out what the call stack is doing as you go through the recursion section. If you get lost like I did several times while working out this problem, if you still have any questions, or if you just want to connect, please reach out to me on LinkedIn. If you have a more optimized or iterative solution to this problem let me know!

The Startup

Get smarter at building your thing. Join The Startup’s +800K followers.

amkemp

Written by

amkemp

Ann-Marie Kemp is a full stack software engineer living in New York City. She is currently studying algorithms and job hunting for a junior developer position.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

amkemp

Written by

amkemp

Ann-Marie Kemp is a full stack software engineer living in New York City. She is currently studying algorithms and job hunting for a junior developer position.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store