Task is to count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.
Input : The only input line contains an integer n.
Output : Print the answer modulo 109+7.
Constraints : 1≤n≤500
My code
#include <iostream>
#include<vector>
using namespace std;
const int m = 1e9+7;
int n; // input
vector<vector<int>>dp; // for memoization
int solve(int i,int sum){
if(sum==0) return 1; // if sum is zero then we found a solution
if(sum<0 || i>n) return 0;
if(dp[i][sum]!=-1) return dp[i][sum];
return dp[i][sum]= ( (solve(i+1,sum))%m + (solve(i+1,sum-i))%m )%m; // for ith element two choice either take ith element or ignore it
}
int main() {
cin>>n;
int sum= ((n)*(n+1))/2; // sum of first n term
if(sum%2!=0){ // if sum of n numbers is not divisible by two 2 we cann't divide in two subset of equal sum
cout<<0;
return 0;
}
sum=sum/2;
dp.assign(n+1,vector<int>(sum+1,-1));
int ans=solve(1,sum)/2; // if set is divivded in subset A and B then (A and B) and (B and A) will be same.
cout<<ans;
}
This code fails for some test case where i am getting wrong ?