# Partition an array into two sub-arrays with the same sum

Given an array of integers, partition the array into two sub-arrays having the same sum of elements.

For example,

Input: {6, -4, -3, 2, 3}
Output: The two subarrays are {6, -4} and {-3, 2, 3} having equal sum of 2

Input: {6, -5, 2, -4, 1}
Output: The two subarrays are {} and {6, -5, 2, -4, 1} having equal sum of 0

Simple solution would to iterate the array and for each element of the array, we calculate sum of left sub-array and right sub-array. The time complexity of this solution is O(n2).

Output:

6 -4
-3 2 3

## Java

Output:

6 -4
-3 2 3

We can also solve this problem in `O(n)` time and `O(1)` space. The idea is to pre-process the array and calculate sum of all elements present in the array. Then for each element of the array, we can calculate its right sum in `O(1)` time by using below formula:

sum of right sub-array = total sum - sum of elements so far

Output:

6 -4
-3 2 3

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
andrew

The solution presented here is naive. It can only solve the problem when each partition consists of consecutive elements. Take for example:

int arr[] = {5,4,3,1,1,2};

The code fails to find a solution, although 5+3 == 4+1+1+2. The problem is actually NP-complete. Because a correct solution would try each element against the sum of the rest: C(n,1); then any combo of 2 elements against the remaining n-2 ones: C(n,2); then any k-combination against the remaining n-k, etc. (C(n,k) = the binomial term = n!/k!/(n-k)!

This results in a complexity O(Sum(C(n,k))_{k=1,…,n-1}) = O(2^n – 2) = O(2^n). Below is the solution in Haskell, which, with a bit of work, can be converted to C++

— k-combinations

combinations :: [a]->Int->[[a]]
combinations xs 1 = [[x] | x<-xs]
combinations [x] _ = [[x]]
combinations (x:xs) n = if n [a] -> [a] -> [a]
set_diff xs ys = [x | x<-xs, not \$ elem x ys]

— given set xs
— partition into 2 sub-arrays of equal sum
— if sum of all elements is odd then no solution
— else return set of indices among k-combinations
— s.t. the set has same indiceal-sum as complementary
— of set; where indiceal-sum means sum of values at
— given indices:

— partition_by2 xs = [ cs | k<-[1..n-2], cs xs!!i) cs) == sum (map (\i->xs!!i) (set_diff rs cs))]
partition_by2 xs = [ cs | k<-[1..n-2], cs xs!!i) cs

Running this on example above:
partition_by2 [5,4,3,1,1,2]
[[0,2],[0,3,5],[0,4,5],[1,2,3],[1,2,4],[1,3,4,5]]

which is a list of lists of indices for left-sides partitions, only. So, one solution is:
[0,2], which means left-partition made of elements of indices 0 and 2 (against the remaining ones, which are implicit, hence not shown); then another solution is:
[0,3,5] , which means left-partition made of elements of indices 0, 3 and 5; etc.