是否找到n个参数的所有可能的组合（正负）和？

Question

我正在尝试构建一个函数，该函数需要可变数量的参数。

该函数接受n个输入，并计算所有可能的加法和减法之和，例如，如果args为1,2,3

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

最后，函数输出最接近零的和。在这种情况下，答案仅为0。

我在解决如何循环n个参数以使用+和-运算符的所有可能组合时遇到很多问题。

我设法建立了一个将所有变量相加或相减的函数，但是我一直坚持如何处理各种+和-，特别是在考虑多个可能的变量时。

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

我想为任何给定数量的输入（总是整数，正数和负数）计算+和-的所有可能排列。欢迎提出将总和与零进行比较的建议，尽管我还没有尝试过，但宁愿先询问这一部分。谢谢。

Answer 1

我会迭代一个数字的可能位。例如，如果有 3 个参数，则有 3 个位，这些位可表示的最高数字为2 ** 3 - 1、 或 7（当所有 3 个位都设置时，111为 、 或 1+2+4）。然后，从 0 到 7 迭代并检查每个位索引是否已设置。

例如，在第一次迭代中，当数字为 0 时，位为000，对应于+++- 将所有 3 个参数相加。

在第二次迭代中，当数字为 1 时，位为001，对应于-++，因此减去第一个参数，然后添加其他两个参数。

第三次迭代将有2, 或010, 或+-+。

第三次迭代将有3, 或011, 或+--。

第三次迭代将有4, 或100, 或-++。

继续该模式直到结束，同时跟踪到目前为止最接近于零的总数。

如果需要，您还可以在发现小计为 0 时立即返回。

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

[args.length - 1 - bitPos]您可以通过将替换为 来“简化”[bitPos]以获得相同的结果，但它看起来会更混乱 - 例如3( 011, 或+--) 会变成110( --+)。

如果没有所有证明代码按预期工作的日志，它就会短得多：

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

您可以通过任意选择第一位数字的符号来将运算次数减少一半。例如。目前，对于， ( ) 和( )sumAll(9, 1)的答案都是有效的，因为它们都同样接近 0。无论输入如何，如果产生一个最接近 0 的数字，那么也一样，只是符号相反。类似地，如果生成一个最接近 0 的数字，则也会生成一个最接近 0 的数字，但符号相反。通过为第一位数字选择符号，您可能会强制计算结果只有一个符号，但这不会影响算法结果与 0 的距离。89 - 1-81 - 9+--+++-----+++

虽然改进并不多（例如，10 个参数，2 ** 10 - 1-> 1023 次迭代改进为2 ** 9 - 1-> 511 次迭代），但也确实有所改善。

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