Yandex test task

Published on July 22, 2019

Yandex test task

Task


Write a function that from an arbitrary input array selects all combinations of numbers whose sum is 10.

At first glance, the task is simple, all you need to do is write a recursion and iterate over all the values.

Or you can use a binary increment, but in order to iterate over all the values ​​for a vector of numbers of length N, it takes 2 ^ n iterations.

First, we choose a special case, suppose that the array consists of numbers> 0. Later, based on this example, we will implement all cases.

STEP 1


a) Consider one of the special cases - the sum of all elements of the array <10.
The logic is simple, sum (V) <10, then sum (V) -V [i] <sum, that is, if the sum of the combinations will always be less than 10.

b) If sum (V) = 10, then the sum sum (V) -V [i] <sum. The result will be only one v .

STEP 2


We remove everything superfluous from the vector.

As an example, take the array [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 1, 5, 5, 5].

It immediately shows that it makes no sense to look for combinations if the value is> 10, but everything will become immediately clear. if we sort it:

[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20]

At this stage, we can already know for sure that it is necessary to remove all elements greater than 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9 , 9, 10]

But in fact, everything is a little more interesting. we need to limit the vector to the value so that V [0] + V [i] <= 10; where i tend to N; But if V [i] = 10, then we add 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9 to the result , 9]

STEP 3


There are duplicate elements in an already filtered array. If we decompose the vector into sub vectors and calculate their sum, we get something like this
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5 , 5, 5] => 20
[8, 8, 8] => 24
[9,9] => 18

The essence of my thoughts is such that it does not make sense to consider combinations of repeating numbers if their number * value> 10. Then we cut it under the vectors until their sum is less than 10, and add those that are 10 to the result:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [ 2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9,9] => [ 9]

As a result of the 3rd step,
[1, 1, 2, 2, 2, 4, 5, 8, 9]

As you can see, the size of the vector has decreased, from 25 to 9, it is much smaller (remember the number of iterations);

With negative numbers


This is a bit more complicated. we will assume that we have implemented the function of finding combinations for a positive sorted vector based on the previous restrictions.
comb (arr, sum), where sum is the required amount, arr is a vector sorted from positive numbers.

For example, take the vector:
[19, 15, -9, 3, -13, -8, -12, 11, -2, - 10, 0, 7, 17, -17, -14, -15, -11, -6, -12, -10, 9]

1. Break the vector
A = only positive values
B = only negative values
And also see if we have values ​​= 0

2. Sorting We sort the
vectors (positive in increasing, negative in decreasing) We

check the particular case for positive numbers (STEP 1)

3. Checking the positive
We check for positive values
comb (B, 10)

3. Check for negative
we create combinations of all negative numbers, but with the restriction:

(sum of elements modulo) <(sum of all positive) + 10
we find combinations for NEW reference sums (sum of elements by modulus + 10)

4. Equality 0
If the source vector has a value of 0, then we add all combinations + 0 to the result;

As a result of such limitations, on average, when testing values ​​with an array of 28 and 1000 tests long, the time gain is almost 42%

Be careful not to look nervous. The author is not responsible for moral suffering.
function combine(arr, etalon = 10) {
    //--------------------------------------------//
    //-------------  helpers  --------------------//
    // Создание бинарного вектора
    // Create binnary array
    function createBin(length) {
        let bin = [];
        for (let i = 0; i < length; i++) {
            bin[i] = false;
        }
        return bin;
    }
    //Бинарное увеличение на 1 
    //Binnary add 1 bit
    function binAddBit(bin, i = 0) {
        if (i >= bin.length) { return null; }
        if (bin[i] == false) {
            bin[i] = true;
            return bin;
        } else {
            bin[i] = false;
            i++;
            return binAddBit(bin, i);
        }
    }
    function iniq(arr) {
        let result = [];
        let object = {};
        arr.forEach(vector => {
            value = vector.sort(function(a, b) { return a - b });
            key = value.join(',');
            object[key] = value;
        });
        for (var key in object) {
            result.push(object[key]);
        }
        return result;
    }
    // Нахождение комбинаций
    // Ограничение:
    // На вход только положительные без нулей
    // На вход массив осортированный по возрастанию
    // в качестве суммы только положительное значение
    function _combine(arr, sum = 10) {
        let result = [];
        // Частный случай
        if (arr[0] > sum) return [];
        if (arr[0] == sum) return [
            [sum]
        ];
        //1. Ограничиваем вектор 
        let $aKey = {};
        let $a = [];
        let $sum = 0;
        // Нулевой элемент массива
        $aKey[arr[0]] = arr[0];
        $a.push(arr[0]);
        $sum += arr[0];
        let $eqSum = false;
        for (let i = 1; i < arr.length; i++) {
            if ((arr[i] + arr[0]) <= sum) {
                //-----------------------------//
                // count*element < sum
                $aKey[arr[i]] = $aKey[arr[i]] != undefined ? $aKey[arr[i]] += arr[i] : arr[i];
                if ($aKey[arr[i]] < sum) {
                    $a.push(arr[i]);
                    $sum += arr[i];
                }
                //-----------------------------//
                //-----------------------------//
                // count*element = sum
                if ($aKey[arr[i]] === sum) {
                    let $res = [];
                    for (let j = 0; j < (sum / arr[i]); j++) {
                        $res.push(arr[i]);
                    }
                    result.push($res);
                }
                //-----------------------------//
            }
            if (arr[i] == sum) { $eqSum = true; }
        }
        if ($eqSum) { result.push([sum]); }
        if ($sum < sum) return result;
        if ($sum == sum) {
            result.push($a);
            return result;
        }
        // Бинарный инкримент
        let bin = createBin($a.length);
        while (change = binAddBit(bin)) {
            let $sum = 0;
            let $comb = [];
            for (let i = 0; i < change.length; i++) {
                if (change[i] == false) continue;
                $sum += $a[i];
                if ($sum > sum) break; // exit in accumulate
                $comb.push($a[i]);
                if ($sum == sum) {
                    result.push($comb);
                }
            }
        }
        return result;
    }
    //-------------  helpers  --------------------//
    //--------------------------------------------//
    let result = [];
    // Сначала разбиваем массив на положительные и отрицательные значения
    // Потом сортируем - так быстрее
    let zero = false; // Существует ли в массиве нулевые значения
    let posetive = [];
    let negative = [];
    let sumPosetive = 0;
    arr.forEach(element => {
        if (element === 0) { zero = true; }
        if (element < 0) { negative.push(element); }
        if (element > 0) {
            posetive.push(element);
            sumPosetive += element;
        }
    });
    // Сортируем векторы (по модулю)
    posetive.sort(function(a, b) { return a - b });
    negative.sort(function(a, b) { return b - a });
    // Если сумма всех положительных элементов меньше эталона, то 
    // Вектор не имеет значений удовлетворяющих условию
    if (sumPosetive < etalon) return [];
    // Частный случай равенства всех положительных значений
    if (sumPosetive == etalon) {
        result.push(posetive);
        if (zero) {
            let _clone = posetive.slice();
            _clone.push(0);
            result.push(_clone);
        }
        return result;
    }
    // Поиск в векторе из положительных элементов;
    result = result.concat(_combine(posetive, etalon));
    // SUPPLE - Ограничение вектора с положительными числами реализован в методе перебора combinPosetiveLim
    negative = negative.filter(function(value) { return -value <= (sumPosetive + etalon); });
    // Находим все сочетания (использую биннарный инкремент)
    let bin = createBin(negative.length); // Булевый вектор
    while (changeBin = binAddBit(bin)) {
        let sum = etalon;
        let vector = []; // Сохраняем вектор из отрициталеьных чисел 
        for (let i = 0; i < changeBin.length; i++) {
            if (changeBin[i] == false) continue;
            sum -= negative[i];
            vector.push(negative[i]);
        }
        if (sum > (sumPosetive + etalon)) continue;
        let lines = _combine(posetive, sum);
        lines.forEach(value => {
            result.push(vector.concat(value));
        });
    }
    // добавляем элементы с 0
    if (zero) {
        result.forEach(item => {
            let _clone = item.slice();
            _clone.push(0);
            result.push(_clone);
        });
    }
    result = iniq(result);
    return result;
}