Сложение всех элементов массива

244

14 июля 2017, 02:11

Нужно решить следующую задачу:

Имеется массив, содержащий произвольные числа:
[3], [5], [2], [6] ....
Нужно найти суммы всех возможных сложений его элементов и записать их в другой массив. Т.е. получается если в массиве 4 элемента, другой массив должен состоять из 16.

Как реализовать алгоритм?

Answer 1

То есть вам нужно получить все возможные подмножества данного множества.

Самый простой вариант - для множества из N элементов берем число из N битов, и проходим по всем возможным значениям числа (для 4 элементов - от 0000 до 1111, т.е. от 0 до 15). Далее для каждого числа суммируем элементы, соответствующие единицам - типа, для 0011 - третий и четвертый (понятно, что удобнее и логичнее считать с младших битов, так что нулевой и первый :))

Думаю, перевести на конкретный язык проблем не составит.

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