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

help
, ,
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: