неправильная сумма подмножества в O (n ^ 2)

Я знаю, что этот код / ​​логика неверен для решения проблемы суммы подмножества, но не могу понять, почему.

Вычислите сумму всех возможных подмножеств и проверьте, равна ли какая-либо требуемая сумма. Это будет сделано за 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;
}