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

help
, ,
4

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

5

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

6

I guess it can be solved by dp

7

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

8

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

9

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

10

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
11

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?

12

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
13

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
14

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

15

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
16

Thanks! Got it…!

17

why you didn’t start from i=ind?

18

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

1 Like
19

cab u draw recursion tree for this?

20

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.

21

I want recursion tree

22

anybody can make a recursion tree for this pb ?
for above code…

23

This problem is very similar to coin combination problem
S = n(n+1)/2
and it can be divided into two sets of equal only if S is even
so this problem boils down to given an array of integers how many distinct ways you can produce a sum S/2, if there are M ways then answer will be M/2

recursive equation for this will be
dp(0, 0) = 1
if (i<0 and j<0): dp(i, j) = 0
dp(i, j) = dp(i-1, j) + dp(i-1, j-i);

you need to call for (dp(S/2, n))/2

here’s a top down code : ZkC32c - Online C++0x Compiler & Debugging Tool - Ideone.com
this will do :slight_smile: