Skip to content

Instantly share code, notes, and snippets.

@dolvik
Last active May 26, 2016 14:15
Show Gist options
  • Save dolvik/4072e34826dc3cef54572f6c8e62e1b7 to your computer and use it in GitHub Desktop.
Save dolvik/4072e34826dc3cef54572f6c8e62e1b7 to your computer and use it in GitHub Desktop.
Find combinations of numbers in an array with determined sum
var ARR_MIN_LENGTH = 5;
var ARR_MAX_LENGTH = 10;
var arr = getArbitraryArray();
//var arr = [1, 10, 3, 2, 7, 3, 8, 9];
console.log(arr, find(arr, 10));
//arr - массив натуральных чисел.
function find(arr, target) {
var sum = 0;
var res = [];
for (var i = 0; i < arr.length; i++) {
var num = arr[i];
//отсеить элементы, превышающие обозначенную сумму
if (num > target) {
continue;
}
if (num === target) {
res.push([num]);
continue;
}
var nextArr = arr.slice(i + 1);
var nextRes = find(nextArr, target - num);
if (!nextRes.length) {
continue;
}
for (var j = 0; j < nextRes.length; j++) {
res.push([num].concat(nextRes[j]));
}
}
return res;
}
//helper functions
//get random number (taken from MDN)
function getRandomIntInclusive(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
//generate arbitrary array
function getArbitraryArray() {
var length = getRandomIntInclusive(ARR_MIN_LENGTH, ARR_MAX_LENGTH);
var arr = new Array(length);
for (var i = 0; i < length; i++) {
arr[i] = getRandomIntInclusive(0, 10);
}
return arr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment