Skip to content

Instantly share code, notes, and snippets.

@nik-kor
Created March 16, 2014 19:43
Show Gist options
  • Save nik-kor/9588749 to your computer and use it in GitHub Desktop.
Save nik-kor/9588749 to your computer and use it in GitHub Desktop.
/**
* Получение комбинаций чисел, сумма которых равна sum
*
* Всю основную работу делает функция generate(см. комментарий к ней).
*
*
* @param {Array} - input - произвольный входящий массив
* @param {Number} - sum - сумма комбинации чисел
*/
function getCombs(input, sum) {
/**
* Функция генерации комбинаций.
*
* В функции мы проходимся по всем элементам оригинального массива. При этом
* происходит рекурсивный вызов. При вызове:
* - изменяется сумма к "погашению", из нее вычитается текущий элемент(число может быть отрицательным)
* - для поиска передается только срез оригинального массива после текущего элемента
*
* @param {Number} - sum - сумма к "погашению"
* @param {Array} - input - отсортированный массив чисел для поиска комбинаций
* @param {Number} - prev - предыдущий элемент, на котором произошел рекурсивный вызов.
* @return {Array}
*/
var generate = function(sum, input, prev) {
var results = [];
for(var i in input) {
if(sum - input[i] === 0) { //Ура! Сумма погашена
results.push([input[i]]);
} else {
//есть, что сжигать и чем?
if(input.length - 1 > i && sum > input[i]) {
//recursion
var res = generate(sum - input[i], input.slice(i * 1 + 1), input[i]);
/* results */
for(i in res[1]) {
/* prev */
results.push([res[0]].concat(res[1][i]));
}
}
}
}
return prev === undefined ? results : [prev, results];
};
var isNumber = function (n) {
return !Array.isArray(n) && !isNaN(parseFloat(n)) && isFinite(n);
};
input = input
.filter(function(val) { return isNumber(val); })
.sort(function(a, b) { return a - b;});
return generate(sum, input);
}
//tests
function isEqual(a1, a2) {
return Array.isArray(a1) && Array.isArray(a2)
&& a1.length === a2.length
&& JSON.stringify(a1) === JSON.stringify(a2);
}
var fixtures = [
{
input: [-1, 0, 1, 2, 3, 5],
output: [
[-1, 0, 1, 2, 3, 5],
[-1, 1, 2, 3, 5],
[0, 2, 3, 5],
[2, 3, 5]
]
},
{
input: [100, 200, 10, -100, 300],
output: [
[-100, 10, 100],
[10]
]
},
{
input: [200],
output: []
},
{
input: ['a', 5, 3, 2, false, [10]],
output: [
[2, 3, 5],
]
}
],
sum = 10;
fixtures.forEach(function(fix) {
var res = getCombs(fix.input, sum);
console.log('Input:', fix.input);
console.log('Output:', fix.output);
console.log('Results:', res);
console.log("\n");
if(!isEqual(res, fix.output)) {
throw new Error('Arrays have to be equal!');
}
});
console.log('Everithing seems ok');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment