Solution: Pluses and Minuses Coding Problem

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

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
Output:
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());
}
/**
 * @param {Array<Number>} numbers
 * @param {Number} earlierSum Sum of the previous numbers in the recursion.
 * @param {Number} i Index of the current number to be processed.
 * @param {Number} sum
 * @param {Map<Number, Map<Number, Number>} memoize Previously calculated 
       result for earlierSum and i.
 * @return {Number} The number of permutations found.
 */
function calculate(numbers, earlierSum, i, sum, memoize) {
  // There's no more number in the array to process.
  if (i == numbers.length) {
    return (earlierSum == sum) ? 1 : 0;
  }
  // Returns memoized result.
  if (memoize.has(earlierSum) && memoize.get(earlierSum).has(i)) {
    return memoize.get(earlierSum).get(i);
  }
  const resultIfAdd =
    calculate(numbers, earlierSum + numbers[i], i + 1, sum, memoize);
  const resultIfSubstract =
    calculate(numbers, earlierSum - numbers[i], i + 1, sum, memoize);
  // Memoizes the output before returning.
  if (!memoize.has(earlierSum)) {
    memoize.set(earlierSum, new Map());
  }
  memoize.get(earlierSum).set(i, resultIfAdd + resultIfSubstract);
  return memoize.get(earlierSum).get(i);
}

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.