getSummands

Возвращает для произвольного массива все комбинации чисел, сумма которых 10

by Valentin Sarychev

HTML

<link rel="stylesheet" href="http://jasmine.github.io/2.1/lib/jasmine.css">
<script src="http://jasmine.github.io/2.1/lib/jasmine.js"></script>
<script src="http://jasmine.github.io/2.1/lib/jasmine-html.js"></script>
<script src="http://jasmine.github.io/2.1/lib/boot.js"></script>

JavaScript

// Возвращает для произвольного массива все комбинации чисел, сумма которых 10
var getSummands = (function (sum) {
    function isNumber(x) {
        return typeof x === 'number' && isFinite(x);
    }

    // Декоратор для func(arr), оставляющий в массиве arr только числа в порядке возрастания
    function prepare(func) {
        return function (arr) {
            var optimizedArr = arr.filter(isNumber);
            optimizedArr.sort(function (x, y) {
                return x - y;
            });
            return func.call(this, optimizedArr);
        };
    }

    return prepare(function (arr) {
        var results = [];

        // шаг рекурсии, где глубина - длина текущей комбинации
        (function step(startIndex, accSum, accArr) {
            for (var i = startIndex; i < arr.length; ++i) {
                var value = arr[i];
                var newAccSum = accSum + value;

                // завершить шаг, если сумма превысила передел
                if (newAccSum > sum) {
                    return;
                }

                var newAccArr = accArr.slice();
                newAccArr.push(value);

                // завершить шаг, если сумма достигла передела
                if (newAccSum === sum) {
                    // добавить комбинацию в результаты, если она уникальна
                    if (newAccArr.join(' ') !== (results[results.length - 1] || []).join(' ')) {
                        results.push(newAccArr);
                    }
                    return;
                }

                // перейти к следующему шагу, просуммировав i-е число
                step(i + 1, newAccSum, newAccArr);
            }
        })(0, 0, []);

        return results;
    });
})(10);

// ================ тесты ================

describe('getSummands должен возвращать все комбинации чисел, сумма которых 10,', function () {
    it('для пустого массива', function () {
        expect(getSummands([])).toEqual([]);
    });

    it('для массива [10]',...