javascript - 查找数组总和中的哪些数字以目标总和

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 条目的多次添加可能会导致目标总和，但考虑到我需要的所有总和，这可能并不准确寻找。任何人都知道解决这个问题的简单方法吗？

标签： javascriptalgorithmmath

Answer 1

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

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

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

然后，我们可以使用同一张地图直接生成所有可能的方法来获得所有可能的总和，而无需任何更多的搜索/回溯。

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

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

// 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 ] ] }