Powerset для большого размера массива

Question

Я хочу найти сумму всех подмножеств силового набора для массива большого размера (до 1500). Я искал, но не смог найти эффективный алгоритм для этого.

Пример:

array=[1,2,3] 

Ответ:

{} -> 0,{1} -> 1,{2} -> 2,{3} -> 3,{1,2} -> 3,{1,3} -> 4,{2,3} -> 5,{1,2,3} -> 6 

Есть ли эффективный способ сделать это?

Answer 1

Существует 2^n подмножеств массива с n элементами.

Каждый элемент будет присутствовать ровно в половине случаев.

Следовательно, сумма всех подмножеств будет суммой всех элементов, умноженной на 2 ^n-1.