Каждая сумма возможностей элементов

Question

Из данного массива (назовите его numbers [] ), я хочу другой массив ( results [] ), который содержит все возможности суммирования между элементами первого массива.

Например, если у меня есть числа [] = {1,3,5}, результаты [] будут {1,3,5,4,8,6,9,0}.Есть 2 ^ N возможностей.Не имеет значения, появляется ли число два раза, потому что результаты [] будут set

Я сделал это для суммы пар или триплета, и это очень просто.Но я не понимаю, как это работает, когда мы суммируем 0, 1, 2 или n чисел.

Это то, что я сделал для пар:

std::unordered_set<int> pairPossibilities(std::vector<int> &numbers) {
    std::unordered_set<int> results;
    for(int i=0;i<numbers.size()-1;i++) {
        for(int j=i+1;j<numbers.size();j++) {
            results.insert(numbers.at(i)+numbers.at(j));
        }
    }
    return results;
}

Кроме того, предполагая, что числа[] отсортировано, есть ли возможность сортировать результаты [], пока мы его заполняем?

Спасибо!

Answer 1

Должна быть также версия для бинарной резки.Этот вариант немного сложен и использует тот набор ответов, который вы упомянули для фильтрации повторяющихся результатов:

Split the list into 2,  
and generate the list of sums for each half 
  by recursion:
    the minimum state is either 
      2 entries, with 1 result, 
      or 3 entries with 3 results
      alternatively, take it down to 1 entry with 0 results, if you insist
Then combine the 2 halves:
  All the returned entries from both halves are legitimate results
  There are 4 additional result sets to add to the output result by combining:
    The first half inputs vs the second half inputs
    The first half outputs vs the second half inputs
    The first half inputs vs the second half outputs
    The first half outputs vs the second half outputs

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

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

Здесь нет интеллекта, но есть много возможностей для параллельной обработки в рамках шагов рекурсии и объединения.

Answer 2

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

1 3 5
3 5
-----
4 8


1 3 5
5
-----
6

1 3 5
3 5
5
------
9

Добавьте 0 в список в конце.

Другой способ решить эту проблему - создать подмножество массивов элементов вектора и затем суммировать данные вектора каждого массива.например, 1 3 5 = {1, 3} + {1,5} + {3,5} + {1,3,5} после удаления наборов одного элемента.

Имейте в виду, что это всегда легче сказать, чем сделать.Одна маленькая ошибка в реализованном алгоритме потребовала бы много времени в отладке, чтобы выяснить это.=]]

Answer 3

Исходя из ответа «Динамическое программирование», вы можете использовать рекурсивное решение, а затем использовать памятку для кэширования результатов, подход «сверху вниз» в отличие от «снизу вверх» Амита.

vector<int> subsetSum(vector<int>& nums)
{
    vector<int> ans;
    generateSubsetSum(ans,0,nums,0);
    return ans;
}

void generateSubsetSum(vector<int>& ans, int sum, vector<int>& nums, int i)
{
    if(i == nums.size() )
    {
        ans.push_back(sum);
        return;
    }

    generateSubsetSum(ans,sum + nums[i],nums,i + 1);
    generateSubsetSum(ans,sum,nums,i + 1);
}

Result is : {9 4 6 1 8 3 5 0} для набора {1,3,5}

Это просто выбирает первое число по первому индексу i добавляет его к sum и рекурсивно.Как только он возвращается, следует вторая ветвь, sum, без добавления nums[i].Чтобы запомнить это, у вас будет кеш для хранения sum в i.

Answer 4

Это можно сделать с помощью Динамическое программирование (DP) в O(n*W), где W = sum{numbers}.

Это в основном то же самое решение Проблема суммы подмножеств , используя тот факт, что задача имеет оптимальную подструктуру.

DP[i, 0] = true
DP[-1, w] = false          w != 0
DP[i, w] = DP[i-1, w] OR DP[i-1, w - numbers[i]]

Начните с следования приведенному выше решению, чтобы найти DP[n, sum{numbers}].

В результате вы получите:

DP[n , w] = true тогда и только тогда, когда w можно построить из numbers