查找满足某些条件的数组子集

Question

假设给出一个由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;
}

Answer 1

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

下面的 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)))

Answer 2

我想回答我的问题并接受观众的评价。 这是我当前的代码。我会解释的。

假设我们有一个 N 个数字的数组。

在变量 i = 0 的循环中，我们得到 N 个子集及其内部和。如果至少有一个子集的总和是 N 的倍数，它将是一个解决方案。否则，(总和 % N( 的值将取 1 到 (N-1( 之间的一个值。存在 N 个和 (N-1( 个可能的余数。因此，至少存在一对 (n， m( 第 n 和和第 m 和将具有相同的余数，其中 0

下面是查找 n 和 m 的代码。

const arr = [];
const TOTAL_NUM = 5;
for (let i = 0; i < TOTAL_NUM; i++) {
arr.push(parseInt(Math.random() * TOTAL_NUM * 10) + 1);
}
console.log(arr.join(', '));
// find n and m
for (let i = 0; i < TOTAL_NUM; i++) {
let sum = 0;
found = false;
for (let j = i; j < TOTAL_NUM; j++) {
sum += arr[j];
if (sum % TOTAL_NUM === 0) {
found = true;
// output result
console.log('Sum = %d, n = %d, m = %d', sum, i, j);
break;
}
}
if (found) break;
}

如您所见，此代码需要 N * (N-1(/2 循环，并且没有内存。即使对于非常大的 N，也需要几毫秒才能找到 n 和 m。 在我的电脑上找到N = 10000000的解大约需要20~80ms(Core i5 4460 @ 2.90GHz(。