# Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:

• Array: 7 5 9 1 3 9 6
• Remove elements 9 and 1 to form array 7 5 3 9 6 that is divisible into two subarrays of equal sum {7,5,3} and {9,6}

Another example:

• Array: 1 10 100
• Whichever subset to remove in the second case, it is not possible to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.

• Please credit the original source of the problem. – John L. Dec 23 '18 at 2:53
• The "continuous subsets" part is definitely helpful, since we have to consider only a polynomial (in terms of n) number of possibilities. – Gassa Dec 23 '18 at 16:16
• Because there are O(n^2) possibles continuous subset (subsequence?) and we could find the "separating point" of the two equal sum subsets in O(n), we have a trivial O(n^3) solution. We could reduce the second part to O(lg n) with binary search and prefix sum. Not sure that a O(n^2 lg n) would be enough. Use 64-bit deal with the 1 billion upper bound. – Black Arrow Dec 25 '18 at 7:24
• @BlackArrow, I posted an O(n^2) method – James Waldby - jwpat7 Jun 16 '19 at 20:08
• What is to be the output? Assuming non-empty from both ends of the array, I'd greedily sum from whatever end has the lower partial sum until equal or impossible. – greybeard Nov 8 at 8:04

Let S denote the solution sum. Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method. Let A denote a given array of positive integers. Consider two kinds of partitions of A: (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence. We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind: Let S be a prefix sum of A. We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E. With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous. The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
S=0; U=sum(A); H=U//2; n=len(A); print (A)
for i in range(n):        # prefix = first i elements
S += A[i]
if S>H: break
Esum = 0                # sum of extract E
Etarget = U - 2*S       # required size of E
k = i+1                 # k -> after last element of E
for j in range(i+1, n-1): # j -> first element of E
while Esum < Etarget and k<n-1:
Esum += A[k]
k += 1
if Esum > Etarget:
Esum -= A[j]    # remove first element of E
continue        # go try next E
if Esum < Etarget:
break           # can't extract enough to win; advance i
print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))

• Because no negative numbers are present, a contiguous subsequence beginning at or to the right of some position $j$ and summing to a given value $T$ can be found in $O(n)$ time: Whenever we go over the total, at $\Sigma [j, k) > T$, say, we move the left edge to $j+1$ but we don't need to wind the right edge $k$ all the way back to $j+1$: It must have been that $\Sigma [j, k-1) < T$, since otherwise we would have never incremented $k$ to reach $[j, k)$. Since $\Sigma [j, k-1) < T$ and all numbers are positive, then certainly $\Sigma [j+1, k-1) < T$ too, so it's safe to start from there. – j_random_hacker Nov 8 at 18:32