Поиск суммы всех подмножеств заданного набора

Question

Предложите алгоритм для нахождения суммы всех подмножеств множества.

Например, если k=3 и подмножества {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} , то сумма подмножеств {1}+{2}+{3}+{1+2}+{1+3}+{2+3}+{1+2+3}=24

Answer 1

Для входа {х , & hellip ;, х _п}, возвращение 2 ^N-1 (x + & hellip; + x _n), поскольку каждый термин появляется в этом количестве сумм.

Answer 2

Ответ:

Всего нет. Подмножеств 2^n.
Поскольку нам не требуется пустое множество, то полные требуемые подмножества 2^n - 1. Теперь все, что нам нужно сделать, это просто получить все возможные подмножества.
Этот алгоритм поможет.

void main() 
    { 
    //Total no. of elements in set = n;  
    //Let's say the Set be denoted as P[n] 
    //declare a global variable sum and initialize to 0. 
    for(int i=1;i<=n;i++) 
    { 
    int r = nCi; 
    //here, r = nCi or you can say n combinations i 
    //it's good to write an extra function named something like "nCi" to evaluate nCi and call it when required. 
    //define a new two dimensional array of size "r","i", say s[r][i] 
    for(int k=0;k<r;k++) 
    { 
    //define a function to get all combination array for s[r][i] using "i" elements out of total "n" 
    //This link will help you with best of code for this particular function 
    //<http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/> 
    //now for every particular s[r][i], do this 
    for(int j=0;j<i;j++) 
    { 

    sum = sum + s[r][j]; 
    } 
    } 
     } 
     //display total output 
     printf("%d",sum); 
     } 

Answer 3

Каждый элемент появляется такое же количество раз, которое случается быть 2 ^п-1 где п число элементов. Итак, ответ: подсчитайте сумму элементов в наборе и умножьте его на 2 ^n-1