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.
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
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?