0
$\begingroup$

Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays.

For example, [7,2,5,7,12] can be divided as the following:

  1. [5,2][7] = 7
  2. [5,7][12] = 12
  3. [7,7][2,12] = 14

We need the final answer as 14 because the max possible sum is 14.

I initially tried to generate all possible combinations of from length 1 to N and compare the sums and take intersection between two subsets. But it takes pow(2,N) time.

Is there an efficient algorithm to solve this problem?

Please help how to approach this problem. I have tried state space tree with recursion like in the problem subset_sum. But couldn't solve this. Please help.

$\endgroup$
2
$\begingroup$

The problem is NP-hard, by a straightforward reduction from the partition problem. Therefore, you should not expect any efficient algorithm. However, there is a pseudo-polynomial-time algorithm using dynamic programming (see pseudo-polynomial-time algorithm for the partition problem for inspiration).

$\endgroup$
  • $\begingroup$ Can you suggest an efficient way to solve this problem with max 15 array items. I actually tried to generate combinations and comparison. But definitely there must be an efficient way to solve this. Please suggest :) $\endgroup$ – Gokul E Aug 6 '18 at 10:55

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.