CODEWITHSUNDEEP
javascriptalgorithm
tbremer
tbremer

Reputation: 693

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

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

Upvotes: 1

Views: 145

Answers (2)

Amadan
Amadan

Reputation: 198436

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

Upvotes: 1

Balaji Katika
Balaji Katika

Reputation: 3015

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/

Upvotes: 4

Related Questions