1

I have been trying to divide an array into two non empty disjoint subsets such that their sum are equal. 

eg. A = {1,2,3,6,88,55,29}  
one possible answer = 1+2+3  and 6

I have read mit tutorial on balanced partition problem but my constraints are different. I don't have to consider whole of set A(means its not necessary that A1 U A2 would result in A). Also another problem is limit of N. There are at most 100 distinct elements each (<= 100 ) .
I have also read THIS post related to my problem, but I couldn't get anything . 

My present Algo -- 
p[1][a[0]] = 1
for i = 2 to n
   for j = 0 to n*n
     if( p[i][j] >= 2) stop

            p[i][j] += j - a[i] > 0 ? ( p[i-1][j] + p[i-1][j-a[i]] ):0
            p[i][j] += j == a[i] ? 1:0
            p[i][j] += j < a[i] ? p[i-1][j]:0

explanation :

Search for sum j at position i. If we got count at position j >=2 means 
there are more than two possibilities for summing up to j.

HERE is sample working code by me

I know this method cant take care of disjoint sets but I am unable to figure out any other approach.

I am in learning phase of Dynamic Prog. and I find it somewhat difficult. Can someone please help me in finding out the error in my current algorithm.

Community
  • 1
  • 1
Bond
  • 501
  • 2
  • 6
  • 18

1 Answers1

1

It seems your code don't go over all the subsets. The Power Set of a set of size n has 2^n-1 non empty elements, so I think this is the lower limit for the algorithmic complexity. You need to find an appropriate way to enumerate the subsets, as related by this other question on SO

In general subset generation is made by adding elements one by one. This allows you to compute the sum of an individual set in one addition if you use dynamic programming. Indeed, If you you have {1,2,3,6} and you save the value to 12, you just need to add 88 to find the sum of {1,2,3,6,88}.

You can find further optimization aside basic DP. For instance if you test 

 {88} > {1,2,3,6,29}

first then you don't need to test for any subset of {1,2,3,6,29} (the smaller sum) with {88}. At the same time you don't need to test any set containing 88 with {1,2,3,6,29}, as it will be always bigger... Now it requires to use recursion from bigger sets to smaller sets.

Community
  • 1
  • 1
UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • I cannot generate all sub sets ( N being very large ). If I add elements one by one how would I be able to take care of cases like `{1,2,9,50,51}` where 1 and 50 adds to 51 ?? I know basic bitmask algorithm for sub-set generation(for N<=20 ). Please clarify a little bit more. – Bond Jun 10 '12 at 08:27
  • if you cannot generate subsets it is not correct. what if the subset you just skipped was part of the solution (like `1,2,3`)? if N is too large you cannot solve it. – UmNyobe Jun 10 '12 at 08:40