# CSES problem Two Sets II

Your task is to count the number of ways numbers $$1,2,…,n$$ can be divided into two sets of equal sum. For example, if n=$$7$$, there are four solutions: $${1,3,4,6}$$ and $${2,5,7}$$, $${1,2,5,6}$$ and $${3,4,7}$$, $${1,2,4,7}$$ and $${3,5,6}$$, $${1,6,7}$$ and $${2,3,4,5}$$ Input The only input line contains an integer n. Output Print the answer modulo $$1e9+7$$. $$1$$$$n$$$$500$$

Source: cses

My approach: It's a pretty straightforward DP problem, where we follow a loop from $$1$$ to $$n$$ and for each such i in $$1$$ to $$n$$, we fill the sum DP.

    int s=sum/2;
vector<int>dp(s+1);
dp[0]=1;
for(int i=1;i<=n;++i){
for(int k=s;k>=0;--k){
if(k-i>=0){
dp[k] = (dp[k] + dp[k-i])%mod;
}
}
}
int ans=dp[s]/2;


My question is, if I change here the loop from $$1$$ to $$n-1$$ and then output $$dp[s]$$, then the answer is correct, however if I loop from $$1$$ to $$n$$, then output $$dp[s]/2$$, it is incorrect. I think both should be correct since in the second method, I am counting all the possibly ways of making sum=$$n*(n+1)/4$$ and then simply dividing by $$2$$ since we take only $$1$$ out of the $$2$$ sets.

I have figured this out after experimenting some time with the code. The issue was that we cannot divide $$dp[sum]/2$$ since we need modulo inverse to calculate the quotient.