Divide an array into two sub arrays such that their sums are equal and possibly maximum

Question

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.

Answer 1

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).