Clarification of Answer… find the max possible two

Question

I need a clarification of the answer of this question but I can not comment (not enough rep) so I ask a new question. Hope it is ok.

The problem is this:

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: Total elements sum cannot be greater than 1000.

The approved answer says:

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.

What I do not undertand is:

If this was the subset sum problem I could solve it with DP, having a memoization matrix of (N x P), where N is the size of the set and P is the target sum...

But I can not figure it out how I should keep track A+B,A-B (as said for the author of the approved answer). Which should be the dimensions of the memoization matrix ? and how that helps to solve the problem ?

The author of the answer was kind enough to provide a code example but it is hard to me to undertand since I do not know python (I know java).

Answer 1

I think thinking how this solution relates to the single subset problem might be misleading for you. Here we are concerned with a maximum achievable sum, and what's more, we need to distinguish between two disjoint sets of numbers as we traverse. Clearly tracking specific combinations would be too expensive.

Looking at the difference between sets A and B, we can say:

A - B = d
A = d + B

Clearly, we want the highest sum when d = 0. How do we know that sum? It's (A + B) / 2!

For the transition in the dynamic program, we'd like to know if it's better to place the current element in A, B or neither. This is achieved like this:

e <- current element
d <- difference between A and B

(1) add e to A -> d + e

why? 
A = d + B
(A + e) = d + e + B

(2) add e to B -> d - e

why? 
A = d + B
A = d - e + (B + e)

(3) don't use e -> that's simply
  what we already have stored for d

Let's look at Peter de Rivas' code for the transition:

# update a copy of our map, so
# we can reference previous values,
# while assigning new values
D2=D.copy()

# d is A - B
# s is A + B
for d,s in D.items():

  # a new sum that includes element a
  # we haven't decided if a 
  # will be in A or B
  s2 = s + a

  # d2 will take on each value here
  # in turn, once d - a (adding a to B),
  # and once d + a (adding a to A)
  for d2 in [d-a, d+a]:

    # The main transition:
    # the two new differences,
    # (d-a) and (d+a) as keys in
    # our map get the highest sum
    # seen so far, either (1) the
    # new sum, s2, or (2) what we
    # already stored (meaning `a`
    # will be excluded here)
    # so all three possibilities
    # are covered.
    D2[abs(d2)] = max(D2[abs(d2)], s2)

In the end we have stored the highest A + B seen for d = 0, where the elements in A and B form disjoint sets. Return (A + B) / 2.