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 :stuck_out_tongue:

link for the problem?

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

https://cses.fi/problemset/task/1093

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.
see in your example you will get it,if won’t reply back

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?

Check this code Number of ways numbers 1,2,…,n can be divided into two sets of equal sum - #12 by sikh_coder

You will figure it out.