Here we have to find number of ways such that numbers 1,2...n can be divided into two sets having equal sum

Key Observations: - -> if sum of numbers 1,2...n is S then sum of each set will be S/2 lets call it target - -> if S%2=1 then we cant divide numbers in two equal sum so in that cae our answer will be 0 - -> Solve it like the problem subset sum equal to k. where our k is target

issues : As we are finding count of all subset having sum = target we will count extra... lets say n=7 then one way to divide is {1,3,4,6} and {2,5,7} but in our approach we will count {1,3,4,6} and {2,5,7} both.

How to solve this issue? : you can observe that if numbers 1,2,...n is divided in two sets say S1 and S2 then any of S1 or S2 must have element n. so we will count only for elements 1,2,...n-1 so that only one of S1 or S2 is counted.

#include<bits/stdc++.h>
using namespace std;

long long mod = 1000000007;
long long dp[70001];

int main(){
    int n; cin>>n;
    long long sum = (1ll*n*(n+1))/2;
    if(sum%2){
        cout<<0<<endl;
        return 0;
    }
    long long target = sum/2;

    dp[0]=1;
    // i<n because as per our logic we are calculating for set not having n, it will be in the opposite set
    for(int i=1;i<n;i++){ 
        for(int j=target;j>=i;j--){
            dp[j] += dp[j-i];
            dp[j]%=mod;
        }
    }
    cout<<dp[target]<<endl;
    return 0;
}