A naive, trivial and still pseudo-polynomial solution would be to use the existing solution to subset-sum, and repeat for sum(array)/2
to 0 (and return the first one found).
Complexity of this solution will be O(W^2*n)
where W
is the sum of the array.
pseudo code:
for cand from sum(array)/2 to 0 descending:
subset <- subsetSumSolver(array,cand)
if subset != null:
return subset
The above will return the maximal subset that is lower/equals sum(array)/2
, and the other part is the complement for the returned subset.
However, the dynamic programming for subset-sum should be enough.
Recall that the formula is:
f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)
When building the matrix, the above actually creates you each row with value lower than the initial x
, if you input sum(array)/2 - it's basically all values.
After you generate the DP matrix, just find the maximal value of x
such that f(x,n)=true
, and this is the best partition you can get.
Complexity in this case is O(Wn)