Тестовая задачка Яндекса -13



Задача


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

С первого взгляда, задача простая, всего то надо написать рекурсию и перебрать все значения.

Или можно использовать двоичный инкремент но для того чтобы перебрать все значения для вектора чисел длинной N, потребуется 2^n итераций.

Для начала выберем частный случай, предположим что массив состоит из чисел > 0. Позже на основе этого примера мы реализуем все случаи.

ШАГ 1


а) Рассмотрим один из частных случаев — сумма всех элементов массива < 10.
Логика проста, sum(V) < 10, то sum(V)-V[i] < sum, то есть если сумма комбинаций всегда будет меньше 10.

б) Если sum(V) = 10, то сумма sum(V)-V[i] < sum. Результат будет только один V.

ШАГ 2


Удаляем из вектора все лишнее

Как пример возьмем массив [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].

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

[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]

На данном этапе мы можем уже точно знаем что надо удалить все элементы больше 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]

Но на самом деле все немного интереснее. нам нужно ограничить вектор, до того значения чтобы V[0]+V[i] <= 10; где i стремиться к N; Но если V[i] = 10, то в результат мы добавляем 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]

ШАГ 3


В уже отфильтрованном массиве существуют повторяющиеся элементы. Если разложить вектор на под вектора, и посчитать их сумму, то получим что то вроде этого
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[ 5, 5, 5, 5] => 20
[ 8, 8, 8] => 24
[ 9,9] => 18

Суть моих размышлений такая, что не имеет смысл рассматривать комбинации из повторяющихся чисел, если их количество*значение > 10. То есть обрезаем под вектора до того момента, чтобы их сумма была меньше 10, а те что равны 10 добавляем в результат:
[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]

В результате 3 го шага, наш вектор будет следующим
[1, 1, 2, 2, 2, 4, 5, 8, 9]

Как видим размер вектора нас сократился, с 25 до 9, это намного меньше (помним про количество итераций);

С отрицательными числами


Тут немного сложнее. будем предполагать что мы реализовали функцию нахождения комбинаций для положительного отсортированного вектора иcходя из предыдущих ограничений.
comb(arr,sum), где sum — необходимая сумма, arr — вектор отсортированный из положительных чисел

Для примера возьмем вектор:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12, -10, 9]

1. Разбиваем вектор
A = только положительные значения
B = только отрицательные значения
А также смотрим есть ли у нас значения = 0

2. Сортировка
Сортируем вектора (положительные по возрастанию, отрицательные по убыванию)

Проверяем частные случай для положительных чисел (ШАГ 1)

3. Проверка положительных
Проверяем для положительных значений
comb(B,10)

3. Проверка для отрицательных
создаем комбинации из всех отрицательных числе, но с ограничением:

(сумма элементов по модулю) < (сумма всех положительных) + 10
находим комбинации для НОВОЙ эталонной сумм ( сумма элементов по модулю + 10)

4. Равенство 0
Если в исходном векторе есть значение 0, то к результату добавляем все сочетания + 0;

В результате таких вот ограничений, в среднем при тестировании значений с массивом длинной 28 и 1000 тестов, выигрыш по времени почти 42%

Осторожно, слабонервным не смотреть. Автор не несет ответсвеность за моральные страдания
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;
}

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (82):

  1. wibotwi
    /#20418559 / +1

    Очень тяжело читать, поправьте пожалуйста опечатки в тексте. Во многиз браузерах есть встроенный спеллчекер.

  2. usharik
    /#20418583

    Задумался, прокатит ли тут динамическое программирование…

    • neurocore
      /#20418901

      Прокатит. Имеем подзадачи A и B со множествами решений соответственно X и Y, тогда решение задачи A+B будет X*Y (декартово)

      • usharik
        /#20419075

        Создаем массив count[10].

        1. Индекс массива — сумма для которой ищем количество комбинаций. В нулевом элементе будет 1, т.к. ноль можно получить только одним способом, а именно из нуля элементов исходного массива.
        2. Для единичной суммы — считаем количество элементов равных 1 и записываем в count[1]
        3. Для суммы равной двум каждый элемент равный двум даст одну последовательность (count[0]), а равный одному — уже посчитанную в count[1].
        4. Для суммы равной k, i-й элемент массива даст count[k-arr[i]], если он меньше или равен k. Далее все сведется к двум вложенным циклам и сложности O(10*N)~O(N).
        5. Пункт 2 тоже сводится к пункту 4. Количество единиц отдельно считать не надо.

        Но это только подсчет количества, только для положительных чисел и без вытаскивания самих последовательностей.

    • Ketovdk
      /#20422399

      я долго залипал и вроде как не нашел решения лучше, чем meet in the middle с асимптотикой 2^(n/2). Идея:
      Входной массив разделить на две части. Для левой части посчитать всевозможные комбинации и забить в хэш-таблицу с ключем, равным сумме элементов в комбинации и значением, равным списку этих комбинаций с такой суммой(ну или количеству, если нужно только количество).
      Далее перебираем всевозможные комбинации справа и ищем для них в этой таблице подходящее по сумме значение (10- текущая сумма).
      Вроде как до n=40 отрабатывает мгновенно.
      Есть ощущение, что полиномиального решения нет. Если у кого-то есть идеи с полиномиальной сложностью-пишите

      • pan-alexey
        /#20423293

        По вашей логике имеем массив из N элементов, мы разбиваем на N/2. После чего перебираем комбинации для N/2 = 2^(N/2), но у нас 2 массива, поэтому общее количество будет 2^(N/2) * 2^(N/2) = 2^N. Я понял к чему вы имели ввиду, это работает если мы используем многопоточные вычисления

        • Ketovdk
          /#20423361

          вы не правы, на самом деле, мы одну половину считаем полностью, а когда считаем вторую половину, то мы уже знаем, какое именно значение из первой половины нужно (10-текущее значение), а оно уже подсчитано и хранится в хэш-таблице

          • pan-alexey
            /#20423405

            Я не хотел бы спорить с вами, возможно вы и правы. Наиболее удачным будет, если вы попробуете реализовать свою идею, буду очень признателен.

            • Ketovdk
              /#20426915

              вариант, который считает количество ответов
              #include <iostream>
              #include <vector>
              #include<map>
              
              #define var auto
              #define ll long long
              #define ull unsigned long long
              #define end '\n'
              
              using namespace std;
              
              int vSize;
              vector<ll> values;
              bool increase(vector<bool>& input)
              {
              	for (int i = vSize - 1; i >= 0; --i)
              	{
              		if (input[i])
              		{
              			input[i] = false;
              		}
              		else
              		{
              			input[i] = true;
              			return true;
              		}
              	}
              	return false;
              }
              ll calcValue(vector<bool>& input)
              {
              	ll s = 0;
              	for (int i = 0; i < vSize; ++i)
              	{
              		if (input[i])
              			s += values[i];
              	}
              	return s;
              }
              
              int main()
              {
              	ll n;
              	cin >> n;
              	map<ll, ll> answerCnt;
              	vSize = n / 2;
              	for (int i = 0; i < vSize; ++i)
              	{
              		ll x;
              		cin >> x;
              		values.push_back(x);
              	}
              	var flags = vector<bool>(vSize, false);
              	answerCnt[calcValue(flags)]++;
              	while (increase(flags))
              	{
              		answerCnt[calcValue(flags)]++;
              	}
              	vSize = n - vSize;
              	values.clear();
              	for (int i = 0; i < vSize; ++i)
              	{
              		ll x;
              		cin >> x;
              		values.push_back(x);
              	}
              	flags = vector<bool>(vSize, false);
              	ll totalCnt = 0;
              	totalCnt += answerCnt[10 - calcValue(flags)];
              	while (increase(flags))
              	{
              		totalCnt += answerCnt[10 - calcValue(flags)];
              	}
              	cout << totalCnt;
              }


  3. m1ld
    /#20418587 / +5

    Я думаю это вам надо было отправить hr-менеджеру, который вас приглашал на интервью. А не искать сотрудников яндекса тут.

  4. Static_electro
    /#20418591 / -1

    С первого взгляда, задача простая, всего то надо написать рекурсию и перебрать все значения...

    Со второго взгляда задача решается за O(n). Автор, я потерял нить рассуждений после шага 1.

    • MarazmDed
      /#20418645

      Со второго взгляда задача решается за O(n). Автор, я потерял нить рассуждений после шага 1.

      Классическая задача о загрузке рюкзака

      • Static_electro
        /#20418659

        Нет же. При чем тут рюкзак? Там надо набрать как можно больше "вещей", общим "весом" не больше заданного. Здесь — строго пары чисел с точной суммой.


        Upd: сходил на вики, проверить себя, что не путаю задачу о ранце ни с чем другим. Нет, не путаю, NP-полная. Здесь все гораздо проще.

        • mayorovp
          /#20418893 / +1

          А где в задаче сказано про "пары"? Я вижу только упоминание "комбинаций".

          • Static_electro
            /#20420975 / +1

            Точно, ваша правда. А я — невнимательный дурень, увидел знакомые слова и кинулся комментировать, обычно на тестах спрашивают старую добрую задачку про пары. Неужели в Яндексе тестовое с np-полной задачкой?

        • MarazmDed
          /#20419301

          Нет же. При чем тут рюкзак? Там надо набрать как можно больше «вещей», общим «весом» не больше заданного. Здесь — строго пары чисел с точной суммой.

          Берете алгоритм для рюкзачной задачи и модифицируете под себя. Емкость рюкзака = 10. Все что меньше — отбрасываете.

          • Zibx
            /#20419873

            Тут можно докладывать вещи занимающие отрицательную ёмкость.

            • MarazmDed
              /#20420477

              Здесь уже подсказали, что эта задача — задача о сумме подмножеств, которую можно рассматривать как специальный случай рюкзачной задачи.

        • Dolios
          /#20419721

          Комбинации != пары. Пары ищутся за O(n), с комбинациями пока не могу сообразить.

          • Zibx
            /#20419877

            Эта задача очень похожа на слияние двух (да и более) неубывающих последовательностей.

      • pan-alexey
        /#20418701 / +1

        Да, действительно, задача о рюкзаке, должна стремиться, а тут необходимо все варианты. Две разные задачи

    • Ayahuaska
      /#20419345 / +1

      Со второго взгляда задача решается за O(n).

      Как?

      • mayorovp
        /#20419825

        Динамическим программированием. Это же просто вариация задачи о рюкзаке.


        Ну, если точнее, это будет не совсем O(n), а O(n + k), где k — размер ответа.

        • Ketovdk
          /#20421313

          для решения задачи о рюкзаке динамикой необходимо отсутствие отрицательных чисел, а также сумму не строго равную 10-ти, как в этой задаче, а НЕ ПРЕВОСХОДЯЩУЮ 10. И рюкзачная динамика ищет самый большой случай, а не все варианты.

          Кстати, предположение автора использовать в решении общего случая (с отрицательными числами) решение только для положительных в корне не верно, т.к. вы в решении для положительных отмели большое количество чисел, которые могут использоваться в случае с отрицательными. Например: -15 5 5 15. Вы уберете число 15 и потеряете один случай.

          • mayorovp
            /#20421961

            Найти все варианты как раз не проблема: динамикой определяется прежде всего возможность набрать нужную сумму нужным подмножеством — а дальше можно применять обычную рекурсию для перебора вариантов, но уже с ранним отсечением невозможных ветвей. Отсюда и O(n + k).


            А вот отрицательные числа и правда всё портят.

            • Ketovdk
              /#20422127

              как раз таки проблема, потому-что нужно хранить сразу ВСЕ решения для каждого размера, а не только лучшее

              • mayorovp
                /#20422151

                Не "все решения для каждого размера", а "признак возможности для каждого размера и префикса".

                • Ketovdk
                  /#20422165

                  так нет, вам же нужно будет потом их вывести еще, так-что нельзя их терять (ну если надо просто посчитать, то все-равно не признак, а количество).

                  • mayorovp
                    /#20422217 / -1

                    Я же писал, выводить их потом рекурсивным поиском за O(k).

                    • vitaliy2
                      /#20430481

                      Решить задачу за O(n+k) невозможно. Например, используя всего лишь массив из 93668 чисел от 1 до 10000 (10к единиц, 5к двоек, 3333 троек и т.?д.) можно получить 3.6*10106 комбинаций, набирая всего лишь сумму 10000. Один только их вывод займёт бесконечность.

                      • mayorovp
                        /#20430675

                        Один только их вывод займёт бесконечность.

                        Так ведь именно этот фактор я и учёл под буквой k...

                        • vitaliy2
                          /#20430697

                          Я думал k — сокращённый диапазон чисел (который равен искомой сумме при отсутствии отрицательных чисел). Так то итак понятно, что за O(кол-во комбинаций) можно вывести без проблем.

                          Сама по себе задача неинтересная, но очень интересная задача — оценить асимптотику количества комбинаций. Понятное дело, что она не выше O(2?) (т.?к. даже если брать все суммы, то в худшем случае этих сумм никогда не будет больше 2?), но чему конкретно она равна в самом худшем случае, когда мы берём только одну сумму? Вот это интересная задача, но мне лень думать)

                          • vitaliy2
                            /#20431365

                            Асимптотика точно не лучше O(2?/n?), т.?к. существует алгоритм выбора элементов, чтобы вышло не менее 2?/(n?+n)*2 вариантов для определённой суммы.

                            Алгоритм такой: просто берём все числа по порядку от 1 до n. Поскольку повторений среди чисел нет, общее количество их комбинаций — ровно 2?. При этом максимальная их сумма не может превышать (n?+n)/2 (по формуле арифметической прогрессии), а минимальная сумма — 1. Соответственно, суммарное количество возможных сумм равно ровно (n?+n)/2 (от 1 до (n?+n)/2).

                            В итоге имеем 2? комбинаций чисел и (n?+n)/2 разных сумм. Это значит, что даже если бы все эти суммы встречались равномерно, на каждую должно приходиться 2?/(n?+n)*2 комбинаций чисел. В реальности комбинаций на лучшую из сумм будет приходиться ещё больше, т.?к. суммы встречаются неравномерно, но несмотря на это мы всё-равно смогли неслабо увеличить минимальную оценку комбинаций одной суммы в одном из худших случаев.

                            В итоге в худшем случае может попасться как минимум 2?/(n?+n)*2 вариантов суммы либо ещё больше, а насколько больше, я пока не знаю. Но это число точно не превышает 2?, т.?к. даже комбинаций всех сумм не может быть больше, чем 2?. Как итог из-за длинного ответа асимптотика решения не может быть лучше O(2?/n?) (либо является ещё хуже).

                            PS. Скорее всего приведённый алгоритм и есть оптимальный. Превысить 2? мы всё-равно не можем, поэтому всё, что мы можем делать, это улучшать делитель, который равняется (n?+n)/2 или меньше. Но как только мы начнём улучшать его, нам придётся жертвовать 2?, т.?к. это значит, что мы начнём повторять числа, а повторения вместо того, чтобы увеличивать количество комбинаций экспоненциально (2?) увеличивают их линейно. В итоге ради уменьшения n? (которое есть в 2?/(n?+n)*2) мы жертвуем 2?. Глупо. Но это пока не доказательство, просто интуиция. Но если моя интуиция верна, то нормальное решение (которое несложное, но требует O(n*k) памяти, где k — размеры чисел) будет работать за O(2?/n?) или насколько-то дольше (т.?к. я не считал разброс неравномерности сумм).

                            • Ketovdk
                              /#20432613

                              я уже привел алогритм за 2^(n/2) для подсчета количества комбинаций и 2^(n/2) + k, где k-количество ответов для вывода всех вариантов (ну и если элементы могут повторяться, то k в худшем случае 2^(n-1), например когда одна десятка и все нули)
                              Хотя по оценке есть вопросы:

                              (n?+n)/2 (по формуле арифметической прогрессии), а минимальная сумма — 1. Соответственно, суммарное количество возможных сумм равно ровно (n?+n)/2 (от 1 до (n?+n)/2).

                              не понятно, причем тут формула арифметической прогрессии, они не обязательно последовательны. И почему минимальная сумма — 1, если могут быть отрциательные.

                              • vitaliy2
                                /#20433283

                                не понятно, причем тут формула арифметической прогрессии, они не обязательно последовательны. И почему минимальная сумма — 1, если могут быть отрциательные.
                                Они последовательны именно в моём алгоритме. Отрицательных тоже в моём нет.

                                Если бы они были непоследовательны, то общее количество сумм увеличилось бы, и на каждую сумму стало бы приходится меньше вариантов, а нам же нужно наоборот дать верхнюю оценку вариантов.

                                • Ketovdk
                                  /#20433415

                                  ну это не совсем правда, т.к. если они непоследовательны (например одинаковы), то 2^(n-1), пример я привел, следовательно верхняя граница не верна

                                  • vitaliy2
                                    /#20433437

                                    Если они одинаковы, то, наоборот, количество комбинаций резко падает.

                                    Если взять все числа от 1 до 30, у нас есть 1073741824 (2?) их комбинации. Но если все эти числа будут одинаковыми, например, единичками (или любым другим числом), получим всего лишь 31 вариант (n+1).

                                    Возможно, в каких-то случаях выгодно взять немного одинаковых чисел в каком-то диапазоне, по крайней мере у меня нет доказательства, что это неправда, но скорее всего, думаю, это неправда. Даже одно одинаковое число среди всех чисел уменьшит суммарное количество комбинаций уже в 1.33 раза. Если мы сможем на какой-то сумме увеличить более чем в 1.33 раза, то это будет выгодно. Но я не уверен, что сможем вообще (т.?к. та сумма, которая по центру, т.?е. равна (n?+n)/4 итак имеет высокую вероятность встречи).

                                    Я чуть позже прикину кол-во комбинаций на лучшей сумме, из-за неравномерности сумм оно, вероятно, O(2?/n) или что-то типа того (т.?к. чем дальше отклоняемся от центральной суммы, тем ниже вероятность на неё попасть).

                                    • Ketovdk
                                      /#20433473

                                      так я же привел пример, когда n-1 ноль и одна десятка. Тогда понятно, что ответов 2^(n-1)

                                      • vitaliy2
                                        /#20433487

                                        Это почему ещё? Если одна десятка и остальные нули, а ищем десятку, то будет всего лишь n комбинаций, что очень мало.

                                        Первая комбинация 10.
                                        Вторая 10 0
                                        Третья 10 0 0

                                        Последняя 10 0 0 0 … 0 0 0

                                        Суммарно ровно n комбинаций.

                                        • Ketovdk
                                          /#20433523

                                          но это не все комбинации, обычно подразумевается с учетом порядка (ну точнее не с учетом порядка, а с учетом места, то есть один ноль отличается от другого, если стоит на другом месте). Хотя конечно смотря как считать

                                          • vitaliy2
                                            /#20433551

                                            Цитирую:

                                            Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых равна 10
                                            Комбинации чисел, а не их позиций. Т.?е. если есть два нуля — это одинаковые числа, и количество комбинаций при их перестановке не увеличится, т.?к. нам нужна именно комбинации чисел, а не их индексов.

                                            0 и 0 — это абсолютная такая же комбинация, что и 0 и 0 (я кэп), даже несмотря на то, что эти нули были взяты с разных мест.

                                            Вообще для отсутствия разночтения в задачах обычно приводят примеры ответа + подробнее описывают условие. Здесь конечно вина автора. А если не было описано, лучше уточнить на всякий случай.

            • imanushin
              /#20422269

              Найти все варианты как раз не проблема

              А можно всё-таки вас попросить накидать псевдокод? По моим не самым эффективным алгоритмам, просто вывод результата требует O(n*k) сложности. Например, если у вас идут возрастающие числа (ну т.е. 1, 2, 3… n) и надо вывести все комбинации для 2*n.

              • Ayahuaska
                /#20423065

                Там разве не придётся проверить все комбинации?

                ЗЫ.
                Я туплю или в массиве из N-элементов, количество комбинаций будет 2^n-1?

          • pan-alexey
            /#20423641

            -15 не потеряется. В этом и смысл отдельно рассматривать только положительные. Для вашего вектора он попадает в шаг 3. т.е. искомый вектор [-15,5,5,15] => [5,5,15] но значение будет уже не 10 а 25. Т.е, в данном случае и получиться единственное сочетание дает нам сумма 25 = [5,5,15], как результат:
            Только для положительных => [5,5]
            Для отрицательных => [-15*,5,5,15]

            Ответ [ [ 5, 5 ], [ -15, 5, 5, 15 ] ]

  5. ferosod
    /#20418595 / -1

    for (item in list) {
    if (list.contains(10-item)) {
    print(item, 10-item)
    }
    }

    • fireSparrow
      /#20418637 / +1

      Во-первых, это квадратичная сложность.
      Во-вторых, оно не работает для комбинаций из более чем двух чисел.

  6. koropovskiy
    /#20418665

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

    и
    [2, 2, 2, 2, 2] => [2, 2, 2]

    Ок. В результат добавили 2+2+2+2+2, но куда делась четвертая двойка из «вектора»?
    результат 2+2+2+2+1+1 потерян :(

    • pan-alexey
      /#20418695

      да, все верно, ровно до 10, реализовал именно с равенством + Суть моих размышлений такая, что не имеет смысл рассматривать комбинации из повторяющихся чисел, если их количество*значение > 10.

      спасибо за ошибку, исправил

  7. FenixFly
    /#20418673

    Для того, чтобы обработать отрицательные числа, нужно найти наименьшее число в векторе, и сместить все числа в векторе и требуемую сумму на модуль этого числа, считаю что это более правильный подход, поскольку мы не меняем алгоритм.

    • fireSparrow
      /#20418743

      Если каждое слагаемое смещаем на A, то требуемую сумму нужно сместить на (n*A), и n будет отличаться от случая к случаю. И это уже никак не впихнуть в тот же самый алгоритм.

  8. Fyret
    /#20418847

    Уверен, ответом на подобные задачи является алгоритм, оформленный хотя бы в виде псевдокода, и оценка его сложности. Здесь ничего этого нет. А задачка заставляет подумать, это да.

  9. truebest
    /#20418937

    Я, если решал такую задачу, выполнил бы сортировку и отбросил все лишнее большее либо равное 10. А дальше сделал бы алгоритм игры Очко, набирая число для нужного значения, при этом пропуская шаги где предыдущий стартовый элемент, равен следующему. Также можно подумать как зеркальные результаты отбросить(типа 1 + 9 или 9 + 1).

    Актуальные алгоритмы, как из АУЕ сделать программиста!

    • dss_kalika
      /#20418951 / +1

      Отрицательные числа не позволят ограничить диапазон.
      Вопрос ещё с неуникальными элементами )

      • truebest
        /#20419017

        Отрицательные числа не позволят ограничить диапазон.
        Ну а куда деваться если про них не сказано в задании. С другой стороны, можно также проверить сложить все положительные и отрицательные числа в две переменные. Точкой равновесия выбрать 10, при сильном перевесе в отрицательную сторону отбрасывать числа, но тогда и на вход нужно подавать все числа в том числе и больше 10. Все же очко это для положительных чисел.

        • dss_kalika
          /#20419119

          ну так и про строгоположительные не говорилось )
          Да и равновесие, конечно, хороший метод, но что то, мне кажется, он не будет сильно лучше сурового перебора )

          • truebest
            /#20419181

            Надо оформить еще одну статью на хабр от себя и написать свое обдуманное и эффектное решение этой задачи, потом уже обсуждать.
            А по факту это мат задача, тут не программистом а математиком-алгоритмистом надо быть. Это как 2 в 64 возводить в лоб, для этого уже есть алгоритмы, которые просто нужно знать.
            Я скорее хотел сказать, какой подход я бы применил решая эту задачу.

            • MarazmDed
              /#20419719

              А по факту это мат задача, тут не программистом а математиком-алгоритмистом надо быть.

              Воу-воу. А программист не должен быть математиком-алгоритмистом? Точно-точно?

              • truebest
                /#20419783

                Вообще нет. Многие из нас читали книги, типа Рода Стивенса «Алгоритмы», наверное многие знают основные алгоритмы и структуры данные, знают про асимптотическую сложность и тд. НО!
                Задачи разными бывают, например мои коллеги и я программисты, в том числе ПЛИСовики, писали код, на основе алгоритмов, разработанных алгоритмистами и математиками. Потому-что банально не каждый программист знает хорошо цифровую обработку сигналов, не знает как входящий поток байт, обработать и преобразовать требуемый выходной массив. Но в сфере компетенций его находится конечная реализация, на c/c++ или asm она будет решает программист иногда советуясь с алгоритмистом.

                • MarazmDed
                  /#20422817

                  Честно говоря, вопрос был риторическим :) Программист (а не кодер) должен быть и математиком и алгоритмистом. Дискретка, теория графов, теория вероятностей, мат. статистика, линейная алгебра да и матан, чего уж греха таить — это must have для программиста.

                  Другое дело, что правило Парето действует везде: 80% задач — не требуют знаний вообще, 20% задач — требуют глубоких знаний. Но все же, программистом принято считать не аникейщика, а человека, хотя бы краем глаза знакомого с математикой.

  10. oam2oam
    /#20418967 / +1

    Понятно, что для N входных чисел существует 2^N сумм этих чисел. Вопрос стало быть, можем ли мы каким-то способом уменьшить этот перебор? Если нет, то ответ к задаче — O(2^N).

    • pan-alexey
      /#20419029

      Я не пишу что при любых значениях N — скорость будет равнятся какой либо зависимости. в качетве теста на выборке имеется профит в 42%. Это утверждение говорит что количество итераций может варьироваться от 0 до 2^N + C

  11. ihost
    /#20418971

    Это задача о сумме подмножеств и имеет псевдополиномиальное время решения в общем случае.
    Новенькие интересные алгоритмы можно посмотреть здесь или погуглить более широко.
    В любом случае непонятно, почему минусят автора статьи, и тем более откуда предлагаются решения с линейной или квадратичной сложностью: пока не доказано P=NP — это невозможно решить быстрее.

    • GCU
      /#20419095

      Предположу что автора минусят за отвратительный текст.
      «Тестовачая» «состоит из числе»
      Стоило бы проявить капельку уважения к читателям — убрать воду и исправить явные ошибки.
      Если это такой юмор, то он непонятен.

  12. oam2oam
    /#20419031

    Простой пример. Пусть входная последовательность длины N состоит из числа 10 и остальных нулей. Тогда для задачи из статьи есть ровно 2^(N-1) решений — это число 10 и все варианты остальных элементов.

  13. usharik
    /#20419101

    Маленькое обращение к автору. Вы научились пользоваться сортировкой для построения эффективных алгоритмов. Увы, далеко не все задачи решаются с её помощью. Пришло время разобраться с динамическим программированием! Задачи на его применение суперчасто встречаются на собеседованиях из-за их неочевидности для неподготовленного кандидата.

    • pan-alexey
      /#20419187

      Большое спасибо, но с чего вы взяли что я не разобрался с динамическим программированием? Потому что я не использовал рекурсию? Рекурсивные функции оправданны, но в конкретном примере я обошелся без них, но никто не говорит что их нельзя использовать для данной задачки. Если будет время попробую реализовать путем разбиения на множество под векторов с использованием динамического программирования.

      • usharik
        /#20419213

        Возможно я высказался слишком категорично, но то как вы пытаетесь использовать сортировку меня навело на такие мысли. Не в коем разе не хотел вас обидеть и буду рад, если ошибся.

        Из моего личного опыта, сортировка нужна там, где речь идет о поиске, а динамическое программирование, когда задача поиска комбинаций или оптимизации.

    • iroln
      /#20420565

      Задачи на его применение суперчасто встречаются на собеседованиях из-за их неочевидности для неподготовленного кандидата

      Подготовленного в чём? Уметь решать на собеседовании абстрактные задачи методом динамического программирования? Человека берут на работу для участия в олимпиадах по программированию? :)


      Как часто вам в работе приходится решать практические задачи с динамическим программированием, когда нужно было реализовывать именно какой-то алгоритм или часть алгоритма?


      Мне вот один раз всего приходилось для "minimum cost path". В прототипе. Потом всё равно выбросили и взяли production ready библиотеку с алгоритмами на графах.


      Тут просто как раз статья параллельно :)
      https://habr.com/ru/post/460901

  14. cross_join
    /#20419271

    С отрицательными числами получается другая задачка, так как длинная комбинация может включать в себя более короткую. Либо нужно вводить ограничение на поиск минимальных комбинаций, а это тоже меняет дело.
    P.S. Выше заметили, что и при наличии нулей возникает неопределенность.

  15. GCU
    /#20419387

    А в чём смысл сначала сортировать элементы, а потом удалять?
    На мой взгляд эффективнее сначала удалять, а уже потом сортировать остаток.

  16. Spaceoddity
    /#20420679

    Про массив вообще ничего не сказано. С чего ТС решил что там будут только НАТУРАЛЬНЫЕ ЧИСЛА?

    • pan-alexey
      /#20423271

      Эм, а с чего вы взяли что это не будет работать и дробными числами?

      • Spaceoddity
        /#20423325 / -1

        Эм, ну с отрицательными точно не будет работать. Я уж молчу про всякие комплексные числа.
        Да у вас там даже приведения типов нет — а если в массиве будут строки?
        Ну и как это будет работать с [29/3, 1/3]?

  17. Ketovdk
    /#20422145

    есть точное решение за 2^(n/2)+количество ответов через MIM. Ну или просто 2^(n/2) если нужно посчитать количество вариантов, а не выводить их. Есть ощущение, что оно оптимальное. Если заинтересует, могу попробовать описать.

    • pan-alexey
      /#20423273

      Буду признателен

      • Ketovdk
        /#20423367

        я уже написал его наверху, случайно написал этот пост