javascript - 用一组重量平衡秤

Question

我收到以下提示:假设您在秤的一侧有一个重量。给定一系列其他权重，看看天平是否会平衡。您可以在任一侧使用权重，并且不必使用所有权重。

我正在尝试使用 javascript 实现该解决方案，并且能够通过累积权重直到出现匹配来解决其中一种情况的问题。最终这只适用于添加到秤左侧的情况，但考虑到权重也可以添加到右侧，这不是最佳选择。下面是我到目前为止的实现。

const balance = (arrayOfWeights) => {
  //Sort the array and pop off the max number to be stored on the right side of the scale 
  let right = arrayOfWeights.sort().pop();
  let balanced;
  let weight;

  const subroutine = (lSide, rSide, weightList) => {
    //Determine if there is a direct match
    if(lSide === rSide) {
      balanced = true;
      return balanced;
    }
    //Return false if a match hasn't been found
    if(weightList.length === 0) {
      balanced = false;
      return balanced
    }
    //Shift the first element of the array to be added to left side
    weight = weightList.shift();
    subroutine(lSide + weight , rSide, weightList);
  }
  subroutine(0, right, arrayOfWeights);
  return balanced;
};

//Array of weights to be passed to balance function
let weights = [3,6,2,5,1];

Answer 1

这是最近复活的老问题。到目前为止给出的答案都没有尝试按照要求使用 Javascript 执行此操作。这是一个应该有效的方法，但不会因效率而赢得任何奖项。几乎可以肯定有一些著名的算法会比这做得更好(在最坏的情况下是 O (n ^ 2)。)但这至少是相当优雅的。

const canBalance = ([w, ...ws], left = 0, right = 0) => 
  left == right && left + right > 0
    ? true
  : w == undefined
    ? false
  : canBalance (ws, left, right) ||
    canBalance (ws, left + w, right) ||
    canBalance (ws, left, right + w)


console .log (canBalance ([3, 6, 2, 5, 1]))  //=> true
console .log (canBalance ([1, 2, 4, 8, 16])) //=> false
console .log (canBalance ([5, 5]))           //=> true

我们有两个简单的案例。如果天平已经平衡(并且不为空)，我们返回 true。如果没有剩余权重，我们返回 false。 (请注意，这些检查必须按此顺序进行，否则我们将错过最后一个重量达到平衡的情况。)

在主要情况下，我们测试三种可能性，如果其中一种为真，则短路。这些情况是，如果我们排除第一个权重，将其放在左侧，或将其放在右侧，然后使用一组较短的权重重复出现。

因为这可能远非最佳，所以我没有费心进行一项明显的优化。我们可以检查所有剩余权重的总和是否小于边之间的差异，如果是，则返回“false”。这将涉及在最终案例之前添加:

  : w + sum (ws) < Math .abs (left - right)
    ? false

使用明显的 sum 函数。