Find Which Numbers in an Array Sum to Target Sums

Question

Doing a little accounting and ran into a problem which I thought I could solve quickly with JavaScript - and then I got stumped. I need to find all of the numbers in an array which when added together will result in my target sums.

Here is my input:

// 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);

I started iterating with a basic for loop adding the numbers together, but realized this is a bit more complex of a problem because multiple additions of the numbersToSum entries may result in target sums but that may not be accurate given all of the sums I need to find. Anyone have a clue as to a simple way to approach this problem?

Answer 1

Here's a fun solution.

First, we build a "sum map" from the array, using a procedure like the classic dynamic programming solution for subset sum.

This map contains, for each possible sum you can create, the list of indexes of possible last numbers in that sum.

We can then use the same map to directly generate all of the possible ways to get all of your possible sums, without any more searching/backtracking.

Note that the output can be very large, but the sum map is not that big for the kinds of inputs you seem to be interested in.

I don't know what you need those big lists for, but maybe you just want to store the sum map instead and generate the lists as you need them. This can save you a lot of memory.

// 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);

Output:

{ '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

This is a classic instance of the Subset Sum problem, a famous NP one. Even though there are a lot of ways of solving it, I will stick to backtracking technique here. Note that this approach will stop on the first correct answer.

The code would become:

// 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);

Furthermore, note this is a very intensive solution, in worst case, we basically bruteforce every possible subset of the array.