Автор Inikon Журидов задал вопрос в разделе Другие языки и технологии
Алгоритм перебора всех комбинаций без повторов и перестановок. и получил лучший ответ
Ответ от Александр Пожарский[гуру]
Можно считать все суммы 2 чисел (их уже может быть меньше, чем сочетаний этих чисел, или хотя бы не больше)
т. е. например 1+3 и 2+2 дадут 1 результат. Суммы складываются в какой-нибудь контейнер с быстрым поиском и добавлением (хеш-таблица? )
Потом считать суммы уже этих сумм с числамиАлександр Пожарский
Просветленный
(22053)
С другой стороны я вот подумал - а ведь таких комбинаций (вида число включено/не включено) будет тоже немало (число сочетаний из числа элементов массива по 1,2,3,...)
Правда тут моему тоже нужна оптимизация - хотя бы предварительной сортировкой. Иначе уже не число комбинаций выходит, а размещений.
В общем быстрый алогритм простым вряд ли будет.
Двоичные числа. Например, для 3 чисел есть 8 комбинаций:
000
001
010
011
100
101
110
111
где 1 - число включено в сумму, 0 - не включено. Заметим, что эти комбинации - это просто двоичные числа от 0 до 7. Дальше ясно?