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.

Saxhorn

It looks like your operations are missing the negative 1s possibilities, eg -1 + 2 + 3, ...`, do you want to exclude those, or do you want to include them? – Disseminule

Good question - yeah, I definitely want to include the possible cases for negative number inputs, but the assumption is that the operators only go between the arguments (so no converting input nums to neg or pos). My example was just not the best illustration. – Saxhorn

This is the optimization variant of the Partition Problem, which is a famous problem. Though it is NP-hard, most instances are not hard. – Lugo

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));

Disseminule

This is a super creative and interesting approach. Thank you - I'm definitely learning a lot here. – Saxhorn

Seems to return -6 for sumAll(90, 70, 10, 67, 44, 13, 24, 92, 37, 1). Correct answer is 0. (cc @goldmund) – Aeolus

@גלעדברקן The output was as expected for the first snippet, but not for the second. I had 2 ** args.length when I needed args.length ** 2. This algorithm has O(2^N) complexity, and yes, that's a lot, it's only brute force, after all – Disseminule

Looks like O(2^n * n) to me :) – Aeolus

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.

Stillman

By subproblems, if you mean redoing calculations, I suppose I could amend the code (I'm still reading through yours so maybe you already did this) to immediately return once it finds a sum of 0. Anyway, this answer is super helpful and nice and concise, so thank you. Going to read through it line by line and make sure I understand everything. – Saxhorn

The problem with immediately returning 0 is that it offers no improvement in the worst case scenario, so it's a pretty insignificant optimization. If there is a way to use dynamic programming here, which I suspect there is, you'd get an enormous speedup in the worst case, so it's worth investigating! You might want to leave the question open for a bit longer to see if anyone else shows up with the insight (or I have a breakthrough). – Stillman

Interesting! I've been reading through the other question - just trying to wrap my head around it. I'm fairly new to the arrow function syntax - I feel like I spent all this time learning JS and suddenly I learn ES6 and there's a lot new. As an aside, one thing I'm wondering is if I wanted to use prompt() to pass user input as the arguments (...nums), is that possible? – Saxhorn

Even with memoization this seems to start getting unwieldy for inputs with a few hundred elements. (cc @goldmund) – Aeolus

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))

Brat

Answer 4

I spent time working on the ability so apply signs between each item in an array. This feels like the most natural approach to me.

const input1 = [1, 2, 3]
const input2 = [1, 2, 3, -4]
const input3 = [-3, 6, 0, -5, 9]
const input4 = [1, 17, 6, 10, 15]

const makeMatrix = (input, row = [{ sign: 1, number: input[0] }]) => {
  if(row.length === input.length) return [ row ]
  const number = input[row.length]
  return [
    ...makeMatrix(input, row.concat({ sign: 1, number })),
    ...makeMatrix(input, row.concat({ sign: -1, number }))
  ]
}

const checkMatrix = matrix => matrix.reduce((best, row) => {
  const current = {
    calculation:  row.map((item, i) => `${i > 0 ? item.sign === -1 ? "-" : "+" : ""}(${item.number})`).join(""),
    value: row.reduce((sum, item) => sum += (item.number * item.sign), 0)
  }
  return best.value === undefined || Math.abs(best.value) > Math.abs(current.value) ? current : best
})

const processNumbers = input => {
  console.log("Generating matrix for:", JSON.stringify(input))
  const matrix = makeMatrix(input)
  console.log("Testing the following matrix:", JSON.stringify(matrix))
  const winner = checkMatrix(matrix)
  console.log("Closest to zero was:", winner)
}
processNumbers(input1)
processNumbers(input2)
processNumbers(input3)
processNumbers(input4)

Silden

Answer 5

I like to join in on this riddle :)

the issue can be described as f_n = f_{n - 1} + a_n * x_n , where x is of X and a₀,...,a_n is of {-1, 1}

For a single case: X * A = y

For all cases X (*) TA = Y , TA = [A_n!,...,A₀]

Now we have n! different A

//consider n < 32
// name mapping TA: SIGN_STATE_GENERATOR, Y: RESULT_VECTOR, X: INPUT    

const INPUT = [1,2,3,3,3,1]
const SIGN_STATE_GENERATOR = (function*(n){
       if(n >= 32) throw Error("Its working on UInt32 - max length is 32 in this implementation")
       let uint32State = -1 >>> 32-n;
       while(uint32State){
          yield uint32State--;
       }
})(INPUT.length)

const RESULT_VECTOR = []
let SIGN_STATE = SIGN_STATE_GENERATOR.next().value
while (SIGN_STATE){
  RESULT_VECTOR.push(
    INPUT.reduce(
      (a,b, index) => 
      a + ((SIGN_STATE >> index) & 1 ? 1 : -1) * b,
      0
    )
  )
  SIGN_STATE = SIGN_STATE_GENERATOR.next().value
}
console.log(RESULT_VECTOR)

Caterwaul