在c语言中查找数组的所有子集以及各个子集的总和到不同的数组

Question

请说明完整的程序...

例如，

a[2] = {3,1};

子集将是

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

各个子集的总和将为

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

数组中各个子集的总和，如

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

编辑：我试过这个：

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

恐怕您的解决方案不起作用：您只是对连续的子集求和。作业告诉您找到 all 个子集。

枚举所有子集的一种简单方法是使用从 0 到 2**n - 1 的循环索引进行迭代，并将索引中的每个低阶 n 位视为包含的指示符在当前子集中。对于 32 位整数，如果可以分配输出数组 (4GB)，则可以使用 unsigned int 作为最多 30 个元素的集合的索引。更大的集合将需要 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;
}

在c语言中查找数组的所有子集以及各个子集的总和到不同的数组

Finding all subsets of an array and sum of the individual subsets to an different array in c language

c

arrays

subset-sum