Solution: Pluses and Minuses Coding Problem

You’re given a list of integers and a sum, S.

Image for post
Image for post

For example:

Array: 1 5 3 4 3
S: 8

Insert, in front of each number, 1 of the 2 symbols, + or -, so that the resulting sum adds up to S.
Write a function that counts all such possibilities.

In the example above, there are 3:

+1 +5 +3 -4 +3
-1 +5 +3 +4 -3
-1 +5 -3 +4 +3

Input: S followed by the list of integers.

Output: The number of possibilities where the sum adds up to S.

Input:
8
1 5 3 4 3

Solution:

Observe:

  1. We need to pick 1 out of the 2 symbols for each number as we move to the next. This suggests that the solution is recursive.

Insights:
Pick a symbol for a number, then recurse on the rest of the numbers to find out how many permutations yield the sum of S.

2. There are 2 possibilities per number, and N numbers in total, so the number of possibilities is 2^N (where N is the length of the array).

Insights:
We can’t brute force through all possibilities and check their sums due to such a large complexity. We need to figure out a way to ignore the majority of the possibilities.

3. As we pick out symbols for the earlier numbers and recurse down on later numbers, notice that the sum of the earlier numbers in many occasions are the same for different permutations.

Examples:
Case 1: +1 -1 +1 ……..
Case 2: +1 +1 -1 ……..
Case 3: -1 +1 +1 ……..
In all 3 cases, the earlier sum is -1.
Hence, if the result of the recursion for case 1 yields 5, which means there are 5 permutations starting with Case 1 that yields the sum of S,
then the results of the recursion for cases 2 and 3 are also 5.

Insights:
We can memoize the result depending on the earlier sum, and return early, skipping out on a lot of possibilities.

Algorithm

Start a recursive function that does the following:

  1. Give the current number the + symbol by creating new sum = old sum + number. Recurse on the rest of the numbers.
  2. Give the current number the — symbol by creating new sum = old sum — number. recurse on the rest of the numbers.
  3. Sum up the results of the previous 2 steps and return it.

Next, add memoization to the function by returning early whenever the sum has been encountered.

Code

/**
* @param {Array<Number>} numbers
* @param {Number} sum
* @return {Number} The number of permutations that yield the correct sum.
*/
function plusesAndMinuses(numbers, sum) {
return calculate(numbers, 0, 0, sum, new Map());
}

Complexity Analysis

Without memoization, the complexity is O(2^N) as explained above.

With memoization, we only calculate the result at most once for each element in the memoize array.

Hence, the complexity for worst-case scenarios is the max size of memoize,
which is O(L * N) where L is all the possible sums that can be achieved.

This range must not go higher than the sum of all the numbers in numbers, and not lower than the negative sum of all the numbers in numbers.

Written by

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Former Intern @Vedantu, Codeforces(Expert)

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