Last active
May 26, 2016 14:15
-
-
Save dolvik/4072e34826dc3cef54572f6c8e62e1b7 to your computer and use it in GitHub Desktop.
Find combinations of numbers in an array with determined sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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