Нахождение всех подмножеств массива и суммы отдельных подмножеств на различные массивы в языке Си

Question

Пожалуйста, укажите полную программу ...

, например,

a[2] = {3,1}; 

подмножества будет

{} 
{3} 
{1} 
{3,1} 

сумма отдельных подмножеств будет

{} -> 0 
{3} -> 3 
{1} -> 1 
{3,1} -> 4 

эта сумма отдельных подмножеств в массиве как

aa[] = {0,3,1,4}; 

EDIT: Я попытался это:

• n является размер массива
• a является входной массив
• aa - это выходной массив, содержащий сумму отдельных подмножеств.

Вот код:

aa[0] = 0; 
z = 1; 
for (c = 1; c <= n; c++) { 
    for (d = 0; d <= n - c; d++) { 
     if (c == 1) { 
      sum1 += a[d]; 
     } else { 
      k = d + c - 1; 
      for (j = k; j < n; j++) { 
       for (i = d; i < k; i++) 
        sum1 += a[i]; 
       sum1 += a[j]; 
      } 
     } 
     aa[z] = sum1; 
     z++; 
     sum1 = 0; 
    } 
} 

Answer 1

Боюсь, ваше решение не работает: вы только суммирование смежных подмножеств. В задании вам будет предложено найти все подмножества.

Простым способом перечисления всех подмножеств является итерация с индексом цикла от 0 до 2**n - 1 и рассмотрение каждого из младших n разрядов в индексе как индикатор включения в текущее подмножество. С 32-битным ints вы можете использовать unsigned int в качестве индекса для наборов до 30 элементов, если вы можете выделить выходной массив (4 ГБ). Для более крупных наборов потребуется 64-битный индекс и генерировать поистине огромный выходной массив.

Вот код:

#include <stdlib.h> 

int *compute_subset_sums(int *a, int n) { 
    int *aa = calloc(1ULL << n, sizeof(int)); 
    if (aa != NULL) { 
     /*---------------------cut here--------------------*/ 
     for (size_t i = 0; (i >> n) == 0; i++) { 
      int sum = 0; 
      for (int j = 0; j < n; j++) { 
       if ((i >> j) & 1) 
        sum += a[j]; 
      } 
      aa[i] = sum; 
     } 
     /*---------------------cut here--------------------*/ 
    } 
    return aa; 
}