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 — Pham Trung
– Pham Trung, Commented Apr 21, 2015 at 4:56

Balaji Katika · Accepted Answer · 2015-04-21 05:04:05Z

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, 2015 at 5:04

Balaji Katika

3,0453 gold badges24 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Amadan · Accepted Answer · 2015-04-21 05:10:06Z

1

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

answered Apr 21, 2015 at 5:10

Amadan

200k23 gold badges252 silver badges321 bronze badges

1 Comment

tbremer Over a year ago

This is close, you are pushing the summand even if there is not a remainder. if (!remainder) { result.push(currAnswer); } else { currAnswer.push(summand); }

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related