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.
[7,2,5,7,12] can be divided as the following:
[5,2] = 7
[5,7] = 12
[7,7][2,12] = 14
We need the final answer as
14 because the max possible sum is
I initially tried to generate all possible combinations of from length
N and compare the sums and take intersection between two subsets. But it takes
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.