O(n^2) 中的错误子集和

Question

我知道这个code/logic对于解决子集和问题是错误的，但似乎无法理解为什么。

计算所有可能子集的总和，并检查是否有任何子集等于所需的总和。这将在 O(n^2) 中完成，这显然是错误的，因为我可以通过 DP O(n*sum) 解决这个问题。

谢谢。

int main() {
    long long int t,n,i,j;
    scanf("%lld",&t);
    while(t--)
    {   
        long long int p[1005][1005],s[1005][1005]={0};
        long long int a[1005],sum;
        long long int counter=0;
        scanf("%lld %lld",&n,&sum);
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        s[0][0]=a[0];
        for(i=0;i<n;i++)
        {   
            for(j=i;j<n;j++)
            {
                if(i==j)
                {
                    s[i][j]=a[i];
                }
                else
                {
                    s[i][j]=a[j]+s[i][j-1];
                }
            }
        }
        int flag=0;
        for(i=0;i<n;i++)
        {
            for(j=i;j<n;j++)
            {
                if(s[i][j]==sum)
                    flag++;
            }
        }
        if(flag)
            cout<<1<<endl;
        else
            cout<<0<<endl;

    }
    return 0;
}

Answer 1

您的代码的问题很简单，就是您没有计算所有子集的总和。这就是为什么您的代码看起来比实际需要的要快得多。

见https://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

问题是 s[i][j] 只记录了 a[i]+a[i+1]+...+a[j]。实际上，您需要记录 a[i...j] 的所有子集的总和，应该是 2^(j-i)。如果您的目标总和不是连续子集的总和，您的代码应该很容易失败。

O(n^2) 中的错误子集和

wrong Subset sum in O(n^2)

subset

dynamic-programming

subset-sum