# Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.

This is my recursive algorithm, what is wrong here?:

int f(int sum,int i){//sum is the current sum, i is the current indx (<=n)
if(i>n){
return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
}
int cnt=f(sum,i+1)+f(sum+i,i+1);//move to i+1 or add i to sum and then move to i+1
return cnt;
}

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}
ie f(0,1)=7


Answer is f(0,1) for any n (n is globally defined)

Thanks!

You are counting the number of ordered pairs of sets $$(A,B)$$ such that the elements of $$A$$ (and of $$B$$) sum to $$n(n+1)/4$$. Simply divide the result by $$2$$ to account for symmetries.
Besides, your algorithm has complexity $$\Omega(2^n)$$ so I doubt you'll meet the time constraint in the link you provided.
You can get an $$O(n^3)$$-time dynamic-programming algorithm as follows:
Let $$OPT[n, x]$$ be the number of ways the numbers in $$\{1, \dots, n\}$$ can be partitioned into an ordered pair of sets $$(A,B)$$ such that the elements of $$A$$ sum to $$x$$ and those of $$B$$ sum to $$n(n+1)/2 - x$$.
Then, $$OPT[0, 0] = 1$$, $$OPT[n][x] = 0$$ if $$n<0$$ or $$x<0$$, and $$OPT[n,x] = OPT[n-1, x-n] + OPT[n-1, x]$$ Now, assuming that $$n(n+1)/2$$ is even, the solution you are looking for is: $$\frac{1}{2}OPT[n][ n(n+1)/4 ]$$.