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

Question

我有一个数组 a[]={1,2,3} 并且我想要这些元素的所有可能组合的单独总和，即； O(n) 复杂度为 1,2,3,1+2,1+3,2+3,1+2+3（单独不是所有子集的总和），数组甚至可以有超过 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;
}

这是我尝试用递归做的事情的图表中的 link 图片 http://uploadpie.com/dQpQp

Answer 1

将此行 for(i=i-1;i>=l;i--) 更改为 for(i=i-1;i>=0;i--)

Answer 2

我会说因为有 2^n 个不同的子数组，在最坏的情况下你可能有 2^n 个不同的总和（当元素相距足够远时会发生这种情况）---你想要显式存储所有这些。所以没有办法在线性时间内解决问题；这是因为您必须 "touch" 每个 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和1 我们首先减去 2，然后减去 3。（如果不删除这些，运行时间会变成 O(n! * 2^n)。）

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

storing sum of each subset of array separately not the total sum of all subsets

c

algorithm

recursion

subset