Algorithm: Every set of numbers that add up to a certain nuber

Question

I am having a hard time reasoning around this problem. Given a set of numbers ([1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11, 12]) I want to find every possible combination that adds up to be 12.

So, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] is equal as is [1, 2, 9] as is [12].

Ideally the return value is something along the lines of...

[
  [1,1,1,1,1,1,1,1,1,1,1,1],
  [1,1,1,1,1,1,1,1,1,1,2],
  …
]

I don't necessarily need the programing solved, just the algo or direction in the algo.

This is what I have so far:

var subsets = function (arr, total, answers, itteration) {
    var answers = answers || [[0]],
        itteration = itteration || 0,
        thisTest = answers[itteration],
        testTotal = sum(thisTest, total);

    if (testTotal === total) {
        if (arr.length === itteration) {
            return answers;
        }

        return subsets(arr, total, answers, itteration++);
    }

    for (var i=0, i<arr.length; i++) {
        thisTest.push(arr[i]);

        if (sum(thisTest, total) === total) {

        }
    }
}

var sum = (array, total) {
    var tempTotal = 0;

    return array.forEach(function (el) {
        return tempTotal += el;
    });
}


console.log(subsets([1,2,3,4,5,6,7,8,9,10,11,12], 12));

This is coin change problem, you can search for that keyword, here is one [example](http://stackoverflow.com/questions/28910971/dynamic-programming-coin-change-problems) — Pham Trung, Apr 21 '15 at 04:56
http://stackoverflow.com/questions/28437488/javascript-coin-changing-change-making-algorithm — adeneo, Apr 21 '15 at 04:58

score 4 · Accepted Answer · answered Apr 21 '15 at 05:04

4

Sounds similar to coin change problem (Dynamic Programing). You could find examples at http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ http://www.geeksforgeeks.org/count-number-ways-reach-given-score-game/

answered Apr 21 '15 at 05:04

Balaji Katika

2,835
2
21
19

score 1 · Answer 2 · answered Apr 21 '15 at 05:10

function exactSum(summands, sum, answer, result) {
  answer = answer || [];
  result = result || [];
  for (var i = 0; i < summands.length; i++) {
    var summand = summands[i];
    var currAnswer = answer.slice();
    var remainder = sum;
    for (var j = 1; remainder >= 0; j++) {
      currAnswer.push(summand);
      remainder -= summand;
      if (!remainder) {
        result.push(currAnswer);
      }
      exactSum(summands.slice(i + 1), remainder, currAnswer, result);
    }
  }
  return result;
}
console.log(exactSum([1, 2, 3], 7));

This is close, you are pushing the summand even if there is not a remainder. `if (!remainder) { result.push(currAnswer); } else { currAnswer.push(summand); }` — tbremer, Apr 21 '15 at 05:29

Algorithm: Every set of numbers that add up to a certain nuber

2 Answers2