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).

C++

Download   Run Code

Output:

6 -4
-3 2 3

Java

Download   Run Code

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

 

Download   Run Code

Output:

6 -4
-3 2 3

 
Thanks for reading.

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 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
andrew
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.