时间戳

首页 > 解决方案 > 找到满足某些条件的数组的子集

javascript - 找到满足某些条件的数组的子集

问题描述

假设给定一个包含 N 个数字的数组。

如何找到一个子集，它的总和是 N 的倍数？

我想知道最好的方法。

递归函数将是正确的选择，但不允许大量 N 的堆栈溢出。

这是我的代码，但它不起作用。 

const arr = [];
const TOTAL_NUM = 5;
let sum = 0;
for (let i = 0; i < TOTAL_NUM; i++) {
    arr.push(parseInt(Math.random() * TOTAL_NUM) + 1);
    sum += arr[i];
}

const mod = sum % TOTAL_NUM;
for (let i = 0; i < TOTAL_NUM; i++) {
    let sum = arr[i]
    let found = false;
    for (let j = i + 1; j < TOTAL_NUM; j++) {
        sum += arr[j];
        if (sum % TOTAL_NUM === 0 || (sum - mod) % TOTAL_NUM === 0) {
            found = true;
            console.log('Sum = %d', sum);
            break;
        }
    }
    if (found) break;
}

标签： javascriptalgorithm

解决方案

我们不一定需要递归。到目前为止，我们可以迭代已知的余数。

下面的 JavaScript 代码（这是详尽的；我们可以有一个更节省空间的版本，通过调整我们存储的内容只返回一个子集）：

// 'rem' stands for "remainder"
function f(A){
  let N = A.length
  let rems = {0: [[]]}
  
  for (let a of A){
    let newRems = {}
    for (let rem in rems){
      let newRem = (a + Number(rem)) % N
      newRems[newRem] = (rems[newRem] || []).concat(
        rems[rem].map(x => x.concat(a)))
    }
    
    newRems[a % N] = (rems[a % N] || []).concat([[a]])
    rems = Object.assign(rems, newRems)
  }

  return rems[0].slice(1)
}

var A = [1, 6, 2, 3, 4]

console.log(JSON.stringify(A))
console.log(`N: ${A.length}`)
console.log(JSON.stringify(f(A)))

推荐阅读