c - 分别存储数组每个子集的总和，而不是所有子集的总和

Question

我有一个数组 a[]={1,2,3}，我想要这些元素的所有可能组合的单独总和，即； 1,2,3,1+2,​​1+3,2+3,1+2+3(单独不是所有子集的总和)，复杂度为 O(n)，数组甚至可以有超过 3 个元素.

#include <stdio.h>
#include <stdlib.h>


int timewaste(int a[],int i,int sum,int l)
{
    sum= sum + a[i];
    printf("%d\n\n",sum);
    if(i==0)
    {
        return 1;
    }
    for(i=i-1;i>=0;i--)
    {
        timewaste(a,i,sum,l);
    }
    return 1;
}

int main()
{
    int i,n,a[50],y,t,pehlibaar;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=n-1;i>=0;--i)
    {
        pehlibaar=0;
        timewaste(a,i,pehlibaar,1);
    }
    return 0;
}

这是我尝试使用递归执行的图表中图像的链接 http://uploadpie.com/dQpQp

Answer 1

我想说，由于有 2^n 个不同的子数组，在最坏的情况下，你可能会有 2^n 个不同的总和(当元素相距足够远时会发生这种情况) )---并且您想显式存储所有这些。所以没有办法在线性时间内解决问题；这是因为您必须“触摸”每个 2^n 总和才能存储它们；这意味着您必须至少进行 2^n 次操作才能访问所有总和。在最坏的情况下，这将花费 O(2^n) 时间。 (更准确地说，我们有运行时间的 Omega(2^n) 下限。)

就算法而言，为什么不从整个总和开始，然后继续减去。这是算法的伪代码。

array = {1, 2, ..., 3} // array of size n
subtracted = {false, false, ..., false}
sum = array[0]+array[1]+...+array[n-1]
visitedArray= {} // hashtable that tels whether we've visited a given array
void all_sums(array, subtracted, sum) {
     // If we've already seen the array, do nothing
     if (visitedArray[array]) return;
     // otherwise, process it
     print sum
     // Remember that we've visited the array, so we don't repeat unnecessary work         
     visitedArray[array] = true;
    // process the current sum---e.g. store wherever you want
    for (i = 0; i < n; ++i) {
        if (!subtracted[i]) {
            subtracted[i] = true;
            all_sums(array, subtracted, sum-array[i])
            subtracted[i] = false;
        }
    }
}

我使用 visiedArray 的原因是为了避免以不同的方式计算相同的总和，例如我们先减去 3 再减去 2 得到的 1我们首先减去 2，然后减去 3，得到 1。(如果不删除这些，运行时间就会变成 O(n! * 2^n) 。 )