javascript - 检查总和为给定值的数组中是否存在可能的值组合

Question

主持人:

假设这是一个重复的问题，并没有解决许多问题。

1. 这个问题不是关于运算符本身如何工作，而是如何它们在算法中起作用，即为什么那些运算符在那个点上。
2. 这道题还包括按位比较“&”运算符，
   其他问题根本没有解决。
3. 所提供答案的核心见解是通过分配
   combinationsCount = 1 << listSize循环中的迭代器“i”成一个位向量，可以针对特定的“j”进行测试以确定是否应包含在要测试的总和中。

我认为这是硬币找零问题变体的解决方案。据我所知，该代码有效，但我不明白最后一个 if 检查是如何进行的:

if (i & (1 << j)) {
    combinationSum += arr[j];
}

适用于此算法(见下文)。我通过教程遇到了它。我真的很感激任何关于这部分代码如何工作的解释。

更新:

明确地说，我了解运算符在做什么，即位移位和逐位加法。我想知道的是它们如何在算法中运行。

possibleCombinationSumN(arr, n) {
  if (arr.indexOf(n) >= 0) {
    return true;
  }

  if (arr[0] > n) {
    return false;
  }

  if (arr[arr.length - 1] > n) {
    arr.pop();
    return possibleCombinationSumN(arr, n);
  }

  var listSize = arr.length, combinationsCount = (1 << listSize)
  for (var i = 1; i < combinationsCount; i++) {
    var combinationSum = 0;
    for (var j = 0; j < listSize; j++) {
      if (i & (1 << j)) {
        combinationSum += arr[j];
      }
    }
    if (n === combinationSum) {
      return true;
    }
  }
  return false;
};

Answer 1

i作为一个位向量(0 和 1 的行)打开或关闭相应数组值参与求和。

例如，如果 arr有 4 个元素，当 i是11 ，它的二进制表示是0b1011 ;这表明我们应该总结arr[3] + arr[1] + arr[0] , 并省略 arr[2] .

现在 - 对于四元素数组，i将从0开始至 15 .为什么？因为1 << arr.length是二进制 0b10000 ( 0b1 向左移动了四个位置)或 16 ，然后我们循环到它的正下方。这为我们提供了 0b0000 之间的二进制值和 0b1111 - 即四个 1 和 0 的所有可能组合。如果我们然后对相应的数组值求和，我们将测试所有可能的总和组合。

i & (1 << j)测试 j 是否- 第一位是 1 .

说 j是3 , 和 i上述11 (0b1011)。 1 << j是0b1000 ; 0b1011 & 0b1000是0b1000 ，这是真实的。在位置 3 有一个, 和 arr[3]进入 combinationSum .

说 j是2 . 1 << j是0b10 ; 0b1011 & 0b100是0b0 , 这是假的。在位置 2 处有一个零; arr[2]不会求和。