Число различных сумм подмножеств

Question

У меня есть набор из N для N> 3 различных целых чисел, и проблема заключается в том, чтобы найти все различные суммы 3-подмножеств заданного множества. 3-подмножество - это подмножество, мощность которого равна 3.

Я знаю, что тупой способ - выполнить кубический поиск по всем возможным суммам, а затем разобрать все дубликаты. Есть ли более эффективный способ сделать это? Я программирую в C.

EDIT: Я хотел знать более общий алгоритм, если бы количество элементов было увеличено.

Answer 1

Использование динамического программирования, вы можете найти номер из различных сумм в O(n*MAX), где MAX является максимальное значение в массиве.

Давайте посмотрим на рекурсивной функции:

f(W,n,i) = f(W,n-1,i) OR (i != 0 ? f(W-item(n),n-1,i-1) : false) 
f(0,0,0) = true 
f(W,n,0) = false (W != 0) 
f(W,0,i) = false (W != 0) 
f(W,n,i) = false (W < 0) 
(I have a feeling I forgot another failing base clause, so make sure if I didn't) 

Теперь, если вы строите это снизу вверх с помощью динамического программирования, до W=3*MAX, ваш ответ в основном число различных W s, что для них f(W,n,3) == true.

Построение таблицы будет O(MAX*3 * n * 3) = O(MAX*n), этап пост-обработки подсчета количества различных W с получением желаемого сумма O(MAX), таким образом, решение остается O(MAX * n)

Answer 2

Если вы подозреваете, что у вас может быть много дубликата сумм, то вы можете сначала вычислить все отчетливые суммы из 2 подмножеств, и для каждой отдельной суммы 2-подмножества, которую вы находите, отслеживайте, какую пару вы нашли, что дало вам сумму. Если все ваши цифры различны, то если вы когда-либо найдете другую пару, которая дает вам ту же сумму, вы должны пометить сумму как «несколько», и вы можете удалить пару, которую вы храните для нее, если хотите. Теперь у вас есть набор из двух подмножеств, и каждая сумма либо имеет одну пару, хранящуюся вместе с ней, либо помечена как «кратная». Для каждой суммы в 2 поднабора, если она помечена как «множественная», вы перебираете все числа в исходном наборе и записываете все суммы в 3 поднабора, которые вы можете сформировать, добавив каждый номер к своей сумме в 2 поднабора. В противном случае, если сумма в 2 поднабора не помечена как «кратная», и у вас есть пара (a, b), связанная с ней, то вы делаете то же самое, кроме пропусков a и b, когда вы выполняете итерирование через ваш исходный набор чисел , Вот как вы получаете все четные суммы из 3 подмножеств. Если у вас есть n чисел, и они делают N отличных сумм из двух подмножеств, то сложность этого подхода - O (nN), если вы используете хеш-таблицы для обнаружения дубликатов на двух этапах алгоритма, которые могут быть намного лучше, чем грубые сила O (n^3 log n), особенно если у вас достаточно плотное множество целых чисел.