Skip to content

Instantly share code, notes, and snippets.

@snit-ram
Last active May 6, 2016 01:10
Show Gist options
  • Save snit-ram/9588d86f0e10813b50f3c1479063a054 to your computer and use it in GitHub Desktop.
Save snit-ram/9588d86f0e10813b50f3c1479063a054 to your computer and use it in GitHub Desktop.
function possibilities(numbers, remaining, expression) {
if (remaining < 0) {
return 0;
} else if (remaining === 0) {
console.log(expression.join(' + '));
return 1;
}
var result = 0;
numbers.forEach(function(number, index) {
var maxTimes = Math.floor(remaining / number);
for (var numberOfTimes = 1; numberOfTimes <= maxTimes; numberOfTimes++) {
result += possibilities(numbers.slice(index + 1), remaining - numberOfTimes * number, expression.concat([numberOfTimes + "x" + number]));
}
});
return result;
}
possibilities([100, 50, 25, 10, 5], 250, []);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment