get_combinations.js

/**
 * Получение комбинаций чисел, сумма которых равна 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');