0
$\begingroup$

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.

This is my recursive algorithm, what is wrong here?:

int f(int sum,int i){//sum is the current sum, i is the current indx (<=n)
    if(i>n){
        return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
    }
    int cnt=f(sum,i+1)+f(sum+i,i+1);//move to i+1 or add i to sum and then move to i+1
    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}
ie f(0,1)=7

Answer is f(0,1) for any n (n is globally defined)

Thanks!

$\endgroup$
2
$\begingroup$

You are counting the number of ordered pairs of sets $(A,B)$ such that the elements of $A$ (and of $B$) sum to $n(n+1)/4$. Simply divide the result by $2$ to account for symmetries.

Besides, your algorithm has complexity $\Omega(2^n)$ so I doubt you'll meet the time constraint in the link you provided.

You can get an $O(n^3)$-time dynamic-programming algorithm as follows:

Let $OPT[n, x]$ be the number of ways the numbers in $\{1, \dots, n\}$ can be partitioned into an ordered pair of sets $(A,B)$ such that the elements of $A$ sum to $x$ and those of $B$ sum to $n(n+1)/2 - x$.
Then, $OPT[0, 0] = 1$, $OPT[n][x] = 0$ if $n<0$ or $x<0$, and $$OPT[n,x] = OPT[n-1, x-n] + OPT[n-1, x]$$ Now, assuming that $n(n+1)/2$ is even, the solution you are looking for is: $\frac{1}{2}OPT[n][ n(n+1)/4 ]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.