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:
[5,2][7] = 7
[5,7][12] = 12
[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.