c - 用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

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

枚举所有子集的一个简单方法是使用从 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;
}