javascript - 查找满足某些条件的数组的子集(Find a subset of an array satisfying some condition)

Question

Suppose that an array of N numbers is given.(假设给出了N个数字的数组。)

How to find a subset that its sum is multiple of N?(如何找到总和为N的倍数的子集？) I want to know the best approach.(我想知道最好的方法。) The recursive function would be the right choice, but stack overflow for large number N isn't allowed.(递归函数将是正确的选择，但是不允许大量N的堆栈溢出。) Here is my code, but it doesn't work.(这是我的代码，但是不起作用。) 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; }   ask by TopW3 translate from so

Answer 1

We don't necessarily need to recurse.(我们不一定需要递归。)

We can iterate on the known remainders so far.(到目前为止，我们可以迭代已知的余数。) JavaScript code below (this is exhaustive; we could have a more space efficient version to return just one subset by adjusting what we store):(下面的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)))