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

Here’s my recursive formula, some how It give’s 1 for all input

``````int f(int sum,int i){
if(i>n){
return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
}
int cnt=0;
cnt=f(sum,i+1)+f(sum+i,i+1)*(i<=n);//i<=n for 2nd eq
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}
///
so f(0,1) should be 4 for n=7
``````

I guess you asked the same question few days ago and got the answer as well by @l_returns

This is different, In that one I had to find one possible answer.

I guess it can be solved by dp

Yes, I know it’s a dp problem. Can you tell whats wrong with my recursive formula?

I can’t understand what your sum and i mean.

sum is the current total sum, i is the selected number (from 1 2 3 4 5 6 7 8 … n)

Make this condition `i>n` to `i==n`
for the second recursive call you need to check if you can call it or not by making
`sum + i < (n*(n+1)/2)`
since this is dp question use dp table for intermediate result.

1 Like

If we are returning when i==n, then we wont be able to add i to the sum when i is n. But still i get the answer. Why?

Isn’t this a binary condition, either it’s equal(1) or not equal(0), So it returns 1, or 0

Didn’t understand this.

A better way to do this problem recursively is to check if certain, elements add upto sum/2 or not.

Here’s a quick code for that:

``````#include <bits/stdc++.h>

using namespace std;

int countPartitions(vector<int> arr,int sum,int ind)
{
if(sum<0) return 0;
if(sum==0) return 1;
if(ind==arr.size()) return 0;

int res=0;

for(int i=ind+1;i<arr.size();i++)
{
res+=countPartitions(arr,sum-arr[i],i);
}
return res;
}

int main() {

int n;cin>>n;
vector<int> arr(n);
int sum=0;
for(int i=0;i<n;i++) arr[i]=i+1;
sum=accumulate(arr.begin(),arr.end(),0);

if(sum%2!=0) {cout<<0;return 0;}

cout<<countPartitions(arr,sum/2,0);

return 0;
}
``````

Just one more thing, it’s not efficient, but turning this recursion into dp table is simple.

1 Like

Since `n` belongs to only one of the set here you are not adding it in sum but when you are checking `2*sum == (n*(n+1)/2)`
you are considering on the other set.

1 Like

If we are considering the other set then it will always have n, Right?

yes
for example `{1,3,4,6} and {2,5,7}`
your sum will be here `1+3+4+6` and you assumed n=7 in other set which is correct.

1 Like

Thanks! Got it…!

why you didn’t start from i=ind?

Because we don’t include same element more than once. So, see one element, and then recurse for rest of them

1 Like

cab u draw recursion tree for this?

You will figure it out.