查找数组中的哪些数字与目标总和求和

Question

做了一点会计，遇到了一个我认为可以用JavaScript快速解决的问题 - 然后我被难住了。我需要在一个数组中找到所有数字，当这些数字加在一起时，将产生我的目标总和。

这是我的意见：

// numbersToSum total = 11319
var numbersToSum = [276, 1872, 1345, 1355, 1400, 1300, 1200, 51, 1020, 500, 400, 300, 100, 100, 100];
// targetSums total = 11319
var targetSums = [1627, 4775, 4917];
// Keep track of the total sum for convenience
var totalSum = 11319;
// Store the solutions
var targetSumsSolutions = [
1627: [],
4775: [],
4917: [],
];
// Do some magic
...
// Output the solutions
console.log(targetSumSolutions);

我开始使用基本的 for 循环迭代将数字相加，但意识到这是一个更复杂的问题，因为多次添加 numbersToSum 条目可能会导致目标总和，但考虑到我需要找到的所有总和，这可能并不准确。有人知道解决这个问题的简单方法吗？

Answer 1

这是一个有趣的解决方案。

首先，我们从数组构建一个"总和图"，使用类似于子集和的经典动态规划解决方案的过程。

对于您可以创建的每个可能的总和，此映射包含该总和中可能最后一个数字的索引列表。

然后，我们可以使用相同的地图直接生成所有可能的方法，以获得所有可能的金额，而无需再进行任何搜索/回溯。

请注意，输出可能非常大，但对于您似乎感兴趣的输入类型，总和图并不大。

我不知道你需要这些大列表做什么，但也许你只是想存储总和图并根据需要生成列表。 这可以为您节省大量内存。

// numbersToSum total = 11319
var numbersToSum = [276, 1872, 1345, 1355, 1400, 1300, 1200, 51, 1020, 500, 400, 300, 100, 100, 100];
// targetSums total = 11319
var targetSums = [1627, 4775, 4917];
// Keep track of the total sum for convenience
var totalSum = 11319;
// Build a "sum map" from a list of positive integers
// For each sum <= maxtarget, the returned map will provide
// the list of indexes that could be the last number in that sum
// From this map, the complete set of possible sums for any value
// can be easily determined.
function buildSumMap(nums, maxtarget)
{
//all accessible sums <= maxtarget
let sumList=[0];
//for each accessible sum, the indexes of possible final numbers, in order
let sumMap={
0:[]
}
for (let i=0; i<nums.length; ++i) {
for (let previ=sumList.length-1; previ>=0; --previ) {
let newsum = sumList[previ]+nums[i];
if (newsum <= maxtarget) {
let list = sumMap[newsum];
if (!list) {
//previously inaccessible sum
sumList.push(newsum);
list = [];
sumMap[newsum] = list; 
}
list.push(i);
}
}
}
return sumMap;
}
// Get all the derivations of a given target sum, using a sum map
// only indexes < indexLimit will be considered
function getSetsThatSum(nums, sumMap, target, indexLimit)
{
if (target==0) {
return [[]];
}
let list = sumMap[target];
if (!(list && list.length)) {
return [];
}
let ret=[];
for (let i=0; i<list.length; i++) {
let lastindex = list[i];
if (lastindex >= indexLimit) {
break;
}
let val = nums[lastindex];
getSetsThatSum(nums, sumMap, target-val, lastindex).forEach(prevsum => {
ret.push([...prevsum, val]);
});
}
return ret;
}
let sumMap = buildSumMap(numbersToSum, 5000);
// Store the solutions
var targetSumsSolutions = {
1627: getSetsThatSum(numbersToSum, sumMap, 1627, numbersToSum.length),
4775: getSetsThatSum(numbersToSum, sumMap, 4775, numbersToSum.length),
4917: getSetsThatSum(numbersToSum, sumMap, 4917, numbersToSum.length),
};
console.log(targetSumsSolutions);

输出：

{ '1627': 
[ [ 276, 1300, 51 ],
[ 276, 1200, 51, 100 ],
[ 276, 51, 500, 400, 300, 100 ],
[ 276, 1200, 51, 100 ],
[ 276, 51, 500, 400, 300, 100 ],
[ 276, 1200, 51, 100 ],
[ 276, 51, 500, 400, 300, 100 ] ],
'4775': 
[ [ 1355, 1200, 1020, 500, 400, 300 ],
[ 1355, 1400, 1020, 500, 400, 100 ],
[ 1355, 1400, 1020, 500, 400, 100 ],
[ 1355, 1300, 1020, 500, 400, 100, 100 ],
[ 1355, 1400, 1020, 500, 300, 100, 100 ],
[ 1355, 1400, 1020, 500, 400, 100 ],
[ 1355, 1300, 1020, 500, 400, 100, 100 ],
[ 1355, 1400, 1020, 500, 300, 100, 100 ],
[ 1355, 1300, 1020, 500, 400, 100, 100 ],
[ 1355, 1400, 1020, 500, 300, 100, 100 ],
[ 1355, 1200, 1020, 500, 400, 100, 100, 100 ],
[ 1355, 1300, 1020, 500, 300, 100, 100, 100 ],
[ 1355, 1400, 1020, 400, 300, 100, 100, 100 ] ],
'4917': 
[ [ 1872, 1345, 1200, 500 ],
[ 1872, 1345, 1300, 400 ],
[ 1872, 1345, 1400, 300 ],
[ 1872, 1345, 1200, 400, 100 ],
[ 1872, 1345, 1300, 300, 100 ],
[ 1872, 1345, 1200, 400, 100 ],
[ 1872, 1345, 1300, 300, 100 ],
[ 1872, 1345, 1200, 300, 100, 100 ],
[ 1872, 1345, 1200, 400, 100 ],
[ 1872, 1345, 1300, 300, 100 ],
[ 1872, 1345, 1200, 300, 100, 100 ],
[ 1872, 1345, 1200, 300, 100, 100 ],
[ 1872, 1345, 1400, 100, 100, 100 ] ] }

Answer 2

这是子集和问题的一个经典实例，一个著名的NP问题。尽管有很多方法可以解决这个问题，但我还是会坚持在这里使用回溯技术。请注意，此方法将在第一个正确答案时停止。

代码将变为：

// numbersToSum total = 11319
var numbersToSum = [276, 1872, 1345, 1355, 1400, 1300, 1200, 51, 1020, 500, 400, 300, 100, 100, 100];
// targetSums total = 11319
var targetSums = [1627, 4775, 4917];
function subsetSum(items, target) {
const input = items.map(() => 0);
const algortihmResponse = subsetSumBacktrack(items, input, target, 0, 0);
return items.filter((element, index) => algortihmResponse[index] === 1);
}
function subsetSumBacktrack(items, response, target, partialSum, totalCheckedElements) {
// Here, we compute the maximum number our partialSum could achieve after adding all the remaining elements
const totalPossibleSum = items
.slice(totalCheckedElements)
.reduce((a, b) => a + b, 0);
// If we've reached our target, just return our response
if (partialSum == target) {
return response;
//  If we've passed our target, just return null. There's no need to continue
} else if (partialSum > target) {
return null;
// If even after summing all the remaining elements we won't reach our target, just return null. There's no need to continue
} else if (partialSum + totalPossibleSum < target) {
return null;
} else {
// Here comes the magic in it. Here we check the next number that will either sum to a number smaller than our target or even, if we are lucky enough, reach the target;
for (const v of [1, 0]) {
response[totalCheckedElements] = v;
const x = subsetSumBacktrack(items, response, target, partialSum + response[totalCheckedElements] * items[totalCheckedElements], totalCheckedElements + 1);
if (x != null) {
return x;
}
}
return null;
}
}
const targetSumsSolutions = targetSums.map(target => subsetSum(numbersToSum, target));
console.log(targetSumsSolutions);

此外，请注意，这是一个非常密集的解决方案，在最坏的情况下，我们基本上暴力破解数组的每个可能子集。