How to optimally divide an array into two subarrays so that sum of elements in both are same, otherwise give an error?

Question

How to optimally divide an array into two subarrays so that sum of elements in both subarrays is same, otherwise give an error?

Example 1

Given the array

10,  20 , 30 , 5 , 40 , 50 , 40 , 15

It can be divided as

10, 20, 30, 5, 40

and

50, 40, 15

Each subarray sums up to 105.

Example 2

10,  20,  30,  5,  40,  50,  40,  10

The array cannot be divided into 2 arrays of an equal sum.

Solution 1

public class Problem1 {

public static void main(String[] args) throws IOException{
    Scanner scanner=new Scanner(System.in);
    ArrayList<Integer> array=new ArrayList<Integer>();
    int cases;
    System.out.println("Enter the test cases");
    cases=scanner.nextInt();

    for(int i=0;i<cases;i++){
        int size;


        size=scanner.nextInt();
        System.out.println("Enter the Initial array size : ");

        for(int j=0;j<size;j++){
            System.out.println("Enter elements in the array");
            int element;
            element=scanner.nextInt();
            array.add(element);
        }
    }

    if(validate(array)){
System.out.println("Array can be Partitioned");}
  else{
     System.out.println("Error");}

}

public static boolean validate(ArrayList<Integer> array){
    boolean flag=false;
    Collections.sort(array);
    System.out.println(array);
    int index=array.size();

    ArrayList<Integer> sub1=new ArrayList<Integer>();
    ArrayList<Integer> sub2=new ArrayList<Integer>();

    sub1.add(array.get(index-1));
    array.remove(index-1);

    index=array.size();
    sub2.add(array.get(index-1));
    array.remove(index-1);

    while(!array.isEmpty()){

    if(compareSum(sub1,sub2)){
        index=array.size();
        sub2.add(array.get(index-1));
        array.remove(index-1);
    }
    else{
        index=array.size();
        sub1.add(array.get(index-1));
        array.remove(index-1);
    }   
    }

    if(sumOfArray(sub1).equals(sumOfArray(sub2)))
        flag=true;
    else
        flag=false;

    return flag;
}

public static Integer sumOfArray(ArrayList<Integer> array){
    Iterator<Integer> it=array.iterator();
    Integer sum=0;
    while(it.hasNext()){
        sum +=it.next();
    }

    return sum;
}

public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
    boolean flag=false;

    int sum1=sumOfArray(sub1);
    int sum2=sumOfArray(sub2);

    if(sum1>sum2)
        flag=true;
    else
        flag=false;

    return flag;
}

}

// The Greedy approach //

Solution 2

There exists a solution, which involves dynamic programming, that runs in O(n*TotalSum), where n is the number of elements in the array and TotalSum is their total sum.

The first part consists in calculating the set of all numbers that can be created by adding elements to the array.

For an array of size n, we will call this T(n),

T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }

(The proof of correctness is by induction, as in most cases of recursive functions.)

Also, remember for each cell in the dynamic matrix, the elements that were added in order to create it.

Simple complexity analysis will show that this is done in O(n*TotalSum).

After calculating T(n), search the set for an element exactly the size of TotalSum / 2.

If such an item exists, then the elements that created it, added together, equal TotalSum / 2, and the elements that were not part of its creation also equal TotalSum / 2 (TotalSum - TotalSum / 2 = TotalSum / 2).

This is a pseudo-polynomial solution. AFAIK, this problem is not known to be in P.

Solution 3

This is called partition problem. There are optimal solutions for some special cases. However, in general, it is an NP-complete problem.

Solution 4

In its common variant, this problem imposes 2 constraints and it can be done in an easier way.

1. If the partition can only be done somewhere along the length of the array (we do not consider elements out of order)
2. There are no negative numbers.

The algorithm that then works could be:

1. Have 2 variables, leftSum and rightSum
2. Start incrementing leftSum from the left, and rightSum from the right of the array.
3. Try to correct any imbalance in it.

The following code does the above:

public boolean canBalance(int[] nums) {
  int leftSum = 0, rightSum = 0, i, j;
  if(nums.length == 1)
      return false;
  for(i=0, j=nums.length-1; i<=j ;){
      if(leftSum <= rightSum){
         leftSum+=nums[i];
         i++;
      }else{
         rightSum+=nums[j];
         j--;
      }
  }
  return (rightSum == leftSum);
}

The output:

canBalance({1, 1, 1, 2, 1})       → true    OK      
canBalance({2, 1, 1, 2, 1})       → false   OK      
canBalance({10, 10})              → true    OK          
canBalance({1, 1, 1, 1, 4})       → true    OK      
canBalance({2, 1, 1, 1, 4})       → false   OK      
canBalance({2, 3, 4, 1, 2})       → false   OK      
canBalance({1, 2, 3, 1, 0, 2, 3}) → true    OK      
canBalance({1, 2, 3, 1, 0, 1, 3}) → false   OK      
canBalance({1})                   → false   OK      
canBalance({1, 1, 1, 2, 1})       → true    OK

Ofcourse, if the elements can be combined out-of-order, it does turn into the partition problem with all its complexity.

Solution 5

a=[int(g) for g in input().split()]     #for taking the array as input in a 
                                     single line
leftsum=0
n=len(a)
for i in range(n):                      
    leftsum+=a[i]                       #calculates the sum of first subarray             
    rightsum=0
    for j in range(i+1):
        rightsum+=a[j]                  #calculates the sum of other subarray
    if leftsum==rightsum:
        pos=i+1                         #if the sum of subarrays are equal, 
        break                           set position where the condition
                                        gets satisfied and exit the loop 
    else:
        pos=-1                          #if the sum of subarrays is not 
                                        equal, set position to -1 
if pos=-1 or pos=n:
    print('It is not possible.')
else:                                   #printing the sub arrays`
    for k in range(n):
        if pos=k:
            print('')
        print(str(a[k]),end='')

View more solutions

Comments

[amit]

indeed it seems NP-complete from first glance, though I didn't think of a proof for it yet. (a proof for it will get you a +1 from me) however, this heuristic seems terrible! probably a greedy solution (try to match every iteration) will outscore this heuristic in most cases.

[Jim Clay]

Unless the odd and even set are exactly the same, element for element, this method is guaranteed to fail.

[soandos]

perhaps the knapsack problem is the wrong way to look at it. I think its may be better to look at it as a bin packing problem, where you instead of changing the number of bins, you change the size of your bins (and make the number of bins 2). it then becomes how do you pack it with least extra space (the point of the bin packing problem). if you can get the extra space in the bins to zero (or equal to each other, which is the same thing) then you have solved it. bin packing is NP-complete. en.wikipedia.org/wiki/Bin_packing_problem

[amit]

@sonados: the wikipedia page says it is even NP-hard. I'll look at this solution later (if it is indeed proves the problem is NPC/NP-Hard). at any case - a full proof that this problem is NPC/NP-Hard worthes to be in the answer body.

[Samarth2011]

Even though it is NP Complete , this way it is proving. For example the test case : Set S={3,19,17,8,16,1,2} . Initial check (sum%2)==0.

[Anirudh Ramanathan]

@Shankar Please read the entire answer before commenting. I mentioned that this is a simpler variant of that problem which is not NP-Complete. [1,3,2] does not have a solution when you consider this variant because it cannot be split along the length into equal sum subsets. This is NOT the partition problem. I am not implying that there is a polynomial time solution for an NP-Complete problem.

[nbro]

What does "The first part consists in calculating the set of all numbers that can be created by adding elements to the array." mean? "...the set of all numbers that can be created". The numbers can be created or the set? "...by adding elements to the array", which array?

[nbro]

"For an array of size n, we will call this T(n)". You call the array of size n T(n)? Why? What does T(n) logically represent?

[nbro]

"Also, remember for each cell in the dynamic matrix, the elements that were added in order to create it.". Not all dynamic programming algorithms require a matrix. A vector sometimes suffices. Can you explain why a matrix is required here? How would this matrix look like, and why? What's the connection between the recursive formulation and the dynamic programming implementation?

[nbro]

"After calculating T(n), search the set for an element exactly the size of TotalSum / 2". Are you saying that we need to look for a number = TotalSum / 2?

[nbro]

"If such an item exists, then the elements that created it, added together, equal TotalSum / 2, and the elements that were not part of its creation also equal TotalSum / 2 (TotalSum - TotalSum / 2 = TotalSum / 2).", not understandable given your previous descriptions. Elements that created a number? What the heck does that mean?

[nbro]

Please, edit this answer with a clear and more exhaustive explanation of "your" algorithm!

[sɐunıɔןɐqɐp]

Welcome to Stack Overflow! Please don't answer just with source code. Try to provide a nice description about how your solution works. See: How do I write a good answer?. Thanks

[Adil H. Raza]

canBalance({ 1, 3, 3, 4, 5 }) should be true but it's returning false...

[Anirudh Ramanathan]

@AdilH.Raza As per the constraint - "partition can only be done somewhere along the length of the array" which is stated at the beginning, ({ 1, 3, 3, 4, 5 }) is expected to be false.

[Selim Yildiz]

How does this solve the problem? A little explanation really improvers your answer.