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.
