Finding all possible combined (plus and minus) sums of n arguments?

Question

I'm trying to build a function that takes a variable number of arguments.

The function takes n inputs and calculates all possible sums of addition and subtraction e.g. if the args are 1,2,3

1 + 2 + 3
1 - 2 - 3
1 + 2 - 3
1 - 2 + 3

Finally, the function outputs the sum that is closest to zero. In this case, that answer would just be 0.

I'm having a lot of problems figuring out how to loop n arguments to use all possible combinations of the + and - operators.

I've managed to build a function that either adds all or subtracts all variables, but I'm stuck on how to approach the various +'s and -'s, especially when considering multiple possible variables.

var sub = 0;
var add = 0;

function sumAll() {
  var i;

  for (i = 0; i < arguments.length; i++) {
    sub -= arguments[i];
  }
  for (i = 0; i < arguments.length; i++) {
    add += arguments[i];
  }
  return add;
  return sub;
};
console.log(add, sub); // just to test the outputs

I'd like to calculate all possible arrangements of + and - for any given number of inputs (always integers, both positive and negative). Suggestions on comparing sums to zero are welcome, though I haven't attempted it yet and would rather try before asking on that part. Thanks.

Answer 1

I'd iterate through the possible bits of a number. Eg, if there are 3 arguments, then there are 3 bits, and the highest number representable by those bits is 2 ** 3 - 1, or 7 (when all 3 bits are set, 111, or 1+2+4). Then, iterate from 0 to 7 and check whether each bit index is set or not.

Eg, on the first iteration, when the number is 0, the bits are 000, which corresponds to +++ - add all 3 arguments up.

On the second iteration, when the number is 1, the bits are 001, which corresponds to -++, so subtract the first argument, and add the other two arguments.

The third iteration would have 2, or 010, or +-+.

The third iteration would have 3, or 011, or +--.

The third iteration would have 4, or 100, or -++.

Continue the pattern until the end, while keeping track of the total closest to zero so far.

You can also return immediately if a subtotal of 0 is found, if you want.

const sumAll = (...args) => {
  const limit = 2 ** args.length - 1; // eg, 2 ** 3 - 1 = 7
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    // eg '000', or '001', or '010', or '011', or '100', etc
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    console.log('i:', i, 'bitStr:', bitStr);
    args.forEach((arg, bitPos) => {
      if (bitStr[args.length - 1 - bitPos] === '0') {
        console.log('+', arg);
        subtotal += arg;
      } else {
        console.log('-', arg);
        subtotal -= arg;
      }
    });
    console.log('subtotal', subtotal);
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

You can "simplify" by replacing the [args.length - 1 - bitPos] with [bitPos] for the same result, but it'll look a bit more confusing - eg 3 (011, or +--), would become 110 (--+).

It's a lot shorter without all the logs that demonstrate that the code is working as desired:

const sumAll = (...args) => {
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

You can cut the number of operations in half by arbitrarily choosing a sign for the first digit. Eg. currently, with sumAll(9, 1), both an answer of 8 (9 - 1) and -8 (1 - 9) would be valid, because they're both equally close to 0. No matter the input, if +- produces a number closest to 0, then -+ does as well, only with the opposite sign. Similarly, if ++--- produces a number closest to 0, then --+++ does as well, with the opposite sign. By choosing a sign for the first digit, you might be forcing the calculated result to have just one sign, but that won't affect the algorithm's result's distance from 0.

It's not much of an improvement (eg, 10 arguments, 2 ** 10 - 1 -> 1023 iterations improves to 2 ** 9 - 1 -> 511 iterations), but it's something.

const sumAll = (...args) => {
  let initialDigit = args.shift();
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = initialDigit;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

Answer 2

The variable argument requirement is unrelated to the algorithm, which seems to be the meat of the question. You can use the spread syntax instead of arguments if you wish.

As for the algorithm, if the parameter numbers can be positive or negative, a good place to start is a naive brute force O(2ⁿ) algorithm. For each possible operation location, we recurse on adding a plus sign at that location and recurse separately on adding a minus sign. On the way back up the call tree, pick whichever choice ultimately led to an equation that was closest to zero.

Here's the code:

const closeToZero = (...nums) =>
  (function addExpr(nums, total, i=1) {
    if (i < nums.length) {
      const add = addExpr(nums, total + nums[i], i + 1);
      const sub = addExpr(nums, total - nums[i], i + 1);
      return Math.abs(add) < Math.abs(sub) ? add : sub;
    }
    
    return total;
  })(nums, nums[0])
;

console.log(closeToZero(1, 17, 6, 10, 15)); // 1 - 17 - 6 + 10 + 15

Now, the question is whether this is performing extra work. Can we find overlapping subproblems? If so, we can memoize previous answers and look them up in a table. The problem is, in part, the negative numbers: it's not obvious how to determine if we're getting closer or further from the target based on a subproblem we've already solved for a given chunk of the array.

I'll leave this as an exercise for the reader and ponder it myself, but it seems likely that there's room for optimization. Here's a related question that might offer some insight in the meantime.

Answer 3

This is also known as a variation of the partition problem, whereby we are looking for a minimal difference between the two parts we have divided the arguments into (e.g., the difference between [1,2] and [3] is zero). Here's one way to enumerate all the differences we can create and pick the smallest:

function f(){
  let diffs = new Set([Math.abs(arguments[0])])
  for (let i=1; i<arguments.length; i++){
    const diffs2 = new Set
    for (let d of Array.from(diffs)){
      diffs2.add(Math.abs(d + arguments[i]))
      diffs2.add(Math.abs(d - arguments[i]))
    }
    diffs = diffs2
  }
  return Math.min(...Array.from(diffs))
}

console.log(f(5,3))
console.log(f(1,2,3))
console.log(f(1,2,3,5))