algorithm - Given an array, you have to find the max possible two equal sum

Question

Given an array, you have to find the max possible two equal sum, you can exclude elements.

i.e 1,2,3,4,6 is given array we can have max two equal sum as 6+2 = 4+3+1

i.e 4,10,18, 22, we can get two equal sum as 18+4 = 22

what would be your approach to solve this problem apart from brute force to find all computation and checking two possible equal sum?

edit 1: max no of array elements are N <= 50 and each element can be up to 1<= K <=1000

edit 2: Here is my solution https://ideone.com/cAbe4g, it takes too much time where given time limit is 5 seconds say for each case.

edit 3:- Total elements sum cannot be greater than 1000.

Answer 1

Recommended approach

I suggest solving this using DP where instead of tracking A,B (the size of the two sets), you instead track A+B,A-B (the sum and difference of the two sets).

Then for each element in the array, try adding it to A, or B, or neither.

The advantage of tracking the sum/difference is that you only need to keep track of a single value for each difference, namely the largest value of the sum you have seen for this difference.

For added efficiency, I recommend you iterate through the elements in order from smallest to largest and stop updating the DP once the largest difference seen so far is reached.

You can also only store the absolute value of the difference, and ignore any difference greater than 25000 (as it will be impossible for the difference to return to 0 from this point).

Python example code

from collections import defaultdict

def max_equal_sum(E):
    D=defaultdict(int)            # Map from abs difference to largest sum
    D[0]=0                        # Start with a sum and difference of 0
    for a in E:                   # Iterate over each element in the array
        D2=D.copy()               # Can keep current sum and diff if element is skipped
        for d,s in D.items():     # d is difference, s is sum
            s2 = s+a              # s2 is new sum
            for d2 in [d-a,d+a]:  # d2 is new difference
                D2[abs(d2)] = max(D2[abs(d2)],s2) # Update with largest sum
        D=D2
    return D[0]/2                 # Answer is half the sum of A+B for a difference of 0

print max_equal_sum([1,2,3,4,6])  # Prints 8
print max_equal_sum([4,10,18,22]) # Prints 22