PlusMinus Challenge: Can you help me understand/explain this recursive solution?

Last week, I received the following challenge in a take-home technical assignment for a position that is most definitely out of my league.

PlusMinus Challenge

Write a function plusMinus(num), with the num parameter being a combination of 1 or more single digits. Determine if it is 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 the string "-++-".

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 "+-+-".

Sample Test Cases
plusMinus(35132) //-++-
plusMinus(199) //not possible
plusMinus(26712) //-+--

I was unsuccessful in solving this during the timed test, but took some time afterwards to try to tackle the problem, with a lot of help from analyzing other people's strategies, solutions, and thought processes.

Strategy Thoughts

From the start, this seemed like a challenge that would require a recursive solution. My initial thought was that I would need to separate the number into an array of digits, and then try adding or subtracting individual digits with one another, one at a time, in an attempt to achieve a final sum of zero. With this sketchy outline of a plan, I was able to start the solution myself, before reaching to outside resources for help.

Converting the Integer to an Array of Integer Digits

First, I needed to convert the given number argument from an integer into an array of integers. This involved the following steps:

1. Convert the num integer into a string of digits: string = num.toString()
2. Split the string into an array of digit strings: stringArray = string.split('')
3. Use the map function to convert each digit string in the array back into an integer: integersArray = stringArray.map(int => parseInt(int))

This process could then be refactored into a one-line conversion:

function plusMinus(num) {
  let a = num.toString().split('').map(int => parseInt(int))

  ...
}

For example, if num = 35132, then a = [3, 5, 1, 3, 2]

Defining a Base Case to Exit the Function

Second, I needed to define a base case that would allow the function to exit. If my strategy roughly involved combining digits through addition or subtraction until there was only one digit left, my base case would have to check the length of the array of digits.

• If there was more than one digit in the array, I would need to call a recursive function to apply the addition/subtraction logic and check to see if the result was equal to zero.
  • If the result was zero, the recursive function would need to exit and return the string of operators.
  • If the result was not zero, the recursive function would be called again, with an updated array and an updated sum.
• However, if there was only one digit in the array, the recursive function would not be called and the program should exit and return "not possible".

  if (a.length < 2) {
    return "not possible"
  }

  // we'll revisit these parameters in the next section
  return recursiveFunc(updatedArray, updatedSum) 

Calling the Recursive Function

This, my friends, is where I needed to do a little / a lot of research and look at other people's solutions and thinking. I had a rough idea of the conditional logic I needed to implement, and a rough idea of the parameters I needed to pass with each recursive call (see description above), but beyond that, I had very little understanding of HOW to implement this.

• How would I iterate through different combinations of pluses and minuses between my integer digits?
• How would I keep track of my string of pluses and minuses as I go?
• How does this all actually come together into a single solution?

Thankfully, I was able to lean on some code examples from Stack Overflow and a few people's personal wikis to help me solidify my understanding and put some of the pieces together.

First, the recursive function would need to take in two parameters, an array and a sum. These would be updated with each call as the array is manipulated and the sum adjusted.

function recursiveFunc(updatedArray, updatedSum) {
...
}

The original function, plusMinus(num), would have to call and return the value of the recursive function that will be outlined below. The updatedArray parameter will be filled in with a shallow copy of the original array of integers, including index 1 through the end of the original array. The updatedSum parameter will be filled with the element at index 0 of the original array.

  return recursiveFunc(a.slice(1), a[0])

For example, if we call plusMinus(35132), the beginning of the solution would look like this:

function plusMinus(35132) {
  let a = num.toString().split('').map(int => parseInt(int))

  if (a.length < 2) {
    return "not possible"
  }

  return recursiveFunc([5, 1, 3, 2], 3)

  ...
}

With this initial call set up, we can now write the recursive function that would, with each call, slice the array and test out adding or subtracting the first element to achieve a final sum.

Building the Recursive Function

We've already set up the parameters for the recursive function. The pseudo-code below outlines the parts that will need to be included in the function.

function recursiveFunc(updatedArray, updatedSum) {

  // A. Define the base case

  // B. Call the recursive function using subtraction

  // C. Call the recursive function using addition

  // D. Return "not possible"
}

A. Define the base case

Check the array length and check whether the combinations equal zero. Exit the conditional and move on to the next line of code if the array length is larger than 1, OR return an operation sign (+ or -) if the array length is equal to one, and the array/sum combo equals zero.

    if (updatedArray.length == 1) {
      if  (updatedSum + updatedArray[0] === 0) {
        return '+'
      } else if (updatedSum - updatedArray[0] === 0) {
        return '-'
      } else {
      return 'not possible'
      }
    }

B. Call the recursive function using subtraction

Add - to the beginning of the operation string if the value is NOT "not possible".

    let string2 = recursiveFunc(updatedArray.slice(1), updatedSum - updatedArray[0])

    if (string2 != 'not possible') {
      return '-' + string2
    }

C. Call the recursive function using addition

Add + to the beginning of the operation string if the value is NOT "not possible"

    let string1 = recursiveFunc(updatedArray.slice(1), updatedSum + updatedArray[0])

    if (string1 != 'not possible') {
      return '+' + string1
    }

D. If nothing else is returned prior to the end of the function, return "not possible"

    return 'not possible'

Breaking down the Recursive Function

Despite my research and testing, this recursive function did not make a whole lot of sense to me until I logged a number of messages into the console to see what exactly was happening at each step.

Here is the code I ran, without console messages:

function plusMinus(num) {
  let a = num.toString().split('').map(int => parseInt(int))

  if (a.length < 2) {
    return "not possible"
  }

  return recursiveFunc(a.slice(1), a[0])

  function recursiveFunc(updatedArray, updatedSum) {

    if (updatedArray.length == 1) {
      if  (updatedSum + updatedArray[0] === 0) {
        return '+'
      } else if (updatedSum - updatedArray[0] === 0) {
        return '-'
      } else {
      return 'not possible'
      }
    }

    let string2 = recursiveFunc(updatedArray.slice(1), updatedSum - updatedArray[0])

    if (string2 != 'not possible') {
      return '-' + string2
    }

    let string1 = recursiveFunc(updatedArray.slice(1), updatedSum + updatedArray[0])

    if (string1 != 'not possible') {
      return '+' + string1
    }

    return 'not possible'
  }
}

...and here is the output I received in the console when I ran plusMinus(35132), with the console.log messages:

So what is happening here?
At the highest level...

1. The plusMinus function is called with an argument of 35132. The integer, 35132 is converted into the array [3, 5, 1, 3, 2].
2. The array length is greater than 2, so the recursiveFunc([5, 1, 3, 2], 3) function is called and the value returned, which gives us our final output of "-++minus", (or "-++-").

At a more granular level...Here is what is happening within step 2 above:

The next 3 calls of the recursiveFunc function that show up in the console can help us understand what is happening under the hood with each call. Essentially, the recursiveFunc function calls itself with updated arguments 3 times before any values are returned.

On the third call of this series of 3 calls, the function is called with the following arguments: recursiveFunc([2], -6).
We finally have an array with a length 1, and we meet the "else" condition on line 85, returning "not possible" since the integer in the array and the sum do not combine to form zero.

At this point, the recursive function continues to be called with an array of one integer, but with different updatedSum values to reflect different combinations of adding and subtracting digits. Many of these combinations do not result in a zero sum, so we keep hitting "not possible" in the else statement on line 85.

However, when recursiveFunc([2], 2) is finally called on the last item of the integer array, we end up with a result of zero, and return a minus from the else if statement on line 82. Note that I changed the + and - to "plus" and "minus" on lines 81 and 84 to better illustrate where the returned values are coming from.

Finally, we start returning values into a results string, starting from the right of the string and working our way to the left. The first value is the minus that is returned from the conditional statement. Then, we add a + to the left of it because it meets the string1 condition, and so on until we return the complete string.

And this is where my understanding is still fuzzy - can anyone help me better understand what is going on with string1 and string2 to build the final output?

Final Solution

function plusMinus(num) {
  let a = num.toString().split('').map(int => parseInt(int))

  if (a.length < 2) {
    return "not possible"
  }

  return recursiveFunc(a.slice(1), a[0])

  function recursiveFunc(updatedArray, updatedSum) {

    if (updatedArray.length == 1) {
      if  (updatedSum + updatedArray[0] === 0) {
        return 'plus'
      } else if (updatedSum - updatedArray[0] === 0) {
        return 'minus'
      } else {
      return 'not possible'
      }
    }

    let string2 = recursiveFunc(updatedArray.slice(1), updatedSum - updatedArray[0])

    if (string2 != 'not possible') {
      return '-' + string2
    }

    let string1 = recursiveFunc(updatedArray.slice(1), updatedSum + updatedArray[0])

    if (string1 != 'not possible') {
      return '+' + string1
    }

    return 'not possible'
  }
}

Have you encountered this challenge in an interview? How did you solve it? I'd love to see other solutions that might be easier to read and/or explain!