I am trying the CSES problem set. I am getting WA on a few tests in Two Sets — II question. Here is the link for the question https://cses.fi/problemset/task/1093

My approach is to create a dp[i][j] which stores the number of ways to get sum i using first j indices. My target is to get sum n*(n-1)/4 . Formula I use is- dp[i][j]=dp[i][j-1]+dp[i-j][j-1];

I initialized dp[0][i] to 1 for all i<=n bcoz the only possible way is to select no indice at all. And also dp[i][0] to 0 for all 1<=i<=target bcoz its not possible to create a sum using no digits at all. I then print (dp[target][n])/2;

Please help. I am getting WA on few tests.

code-

include

include

include

include

include

include

define vi vector

define tests int t; cin>>t; while(t--)

define ll long long

define vll vector

define sort(v) sort(v.begin(), v.end())

define sortg(v) sort(v.begin(), v.end(), greater ())

using namespace std;

char nums[10] = { '0','1','2','3','4','5','6','7','8','9' }; char alphsl[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' }; const ll MOD = 1000000007;

using namespace std;

void solve() {

ll n;
cin >> n; 
if ((n * (n + 1))%4 != 0) {
    cout << 0 << endl;
    return;

}

ll target = (n * (n + 1)) / 4;

vector<vector<ll>> numways(target+1, vector<ll> (n+1, 0));

for (ll i = 0; i < n+1; i++) {
    numways[0][i] = 1;
}

for (ll i = 1; i < target+1; i++) {
    numways[i][0] = 0;
}

for (ll i = 1; i <= target; i++) {
    for (ll j = 1; j < n+1; j++) {
       numways[i][j] = numways[i][j - 1];
       if (i - j >= 0) {
         numways[i][j] += numways[i - j][j - 1];
       }
       numways[i][j] %= MOD;
    }
}

cout << numways[target][n]/2 << endl;

}

int main() {

solve();

return 0;

}