Last Updated: 5 Nov, 2020

Array partition with minimum difference

Hard

Asked in companies

Solve now

Problem statement

You are given an array 'arr' containing 'n' non-negative integers.

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

1. Each array element should belong to exactly one of the subsets.

2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are 
   a) {1,2} and {3}
   b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset.

Example:

Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].

Ouput: 1

Explanation: We can partition the given array into {3, 1, 5} and {2, 8}. 
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).

Input Format:

The first line of input contains integer 'n' denoting the size of the array.

The second line of the input contains 'n' space-separated integers denoting the elements of the array 'arr'.

Output Format:

Return the minimum possible absolute difference.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

This problem can be solved using recursion. And the idea behind this is to generate all the possible sums from the given set.
We will try different combinations for one of the subsets and accordingly calculate the sums of both the subsets and store the minimum. Assume that the sum of elements of the array is ‘sum', and the sum of the elements of the first subset is ‘s1’. Thus, we can find the sum of the 2nd subset as ‘sum’ - ‘s1’.
For each element, we will have two choices: either to include it in the first subset or not. So, at each stage, we will make two recursive calls, one which will consider including the current element and the other which won’t. We will explore the depth considering each of the two possible cases.
When we have no elements to explore, we will consider (abs(('sum' - ‘pathSum’) - ‘pathSum’) as one of the possible answers, where ‘pathSum’ is the subset sum achieved in the current recursive call. And finally, we will be taking the minimum of all such values to get the desired answer.

Solve now

02 Approach

We can think of this problem as the standard problem of dynamic programming, which is to check whether a subset exists with the given 'sum'.

Here we need to find if there is a way to partition a set into two subsets such that the difference between subset sums is minimum. We know that the best possible scenario is when the subset sums of both the subsets are equal, and thus we want both our subsets to have a sum as close to sum/2, where ‘sum’ is the total sum of elements in the array. So to achieve this, we need to check if there exists a subset with a sum up to half the total sum.

So, to do this, we will create a boolean 'dp' table of size ((‘n’+1) * ('sum'/2 + 1)), where the ‘sum’ is the total sum of the array, and ‘n’ is the number of elements in the array.
Here, the value of ‘dp’[i][j] denotes whether or not it is possible to make a subset from the first ‘i’ elements of the array with 'sum' equal to ‘j’.
The base case will be 'dp'[i][0]=true, and 'dp'[0][j]=false for j>0.
Now the loop(loop variable-i) runs through the number of elements:
- Now loop(loop variable-j) runs through 1 to ('sum'/2 + 1):
  - If the value of the ith element is equal to j.
    - 'dp'[i][j] = true.
  - If the value of the ith element is greater than ‘j’, then we can't consider the ith element to achieve the sum = ‘j’.
    - 'dp'[i][j]='dp'[i-1][j]
  - If the value of the ith element is less than ‘j’, then we have two possibilities: to include the ith element or to leave it.
    - 'dp'[i][j]='dp'[i-1][j] | 'dp'[i-1][j- ‘arr’[i - 1]] (‘|’ denotes boolean ‘or’),
Now after computing the 'dp' table as above, we can run a loop for all the columns of the last row from right to left, and at whichever value of j the value in the table is true, we will return abs(‘sum' - 2*’j’), which is our best possible answer.

Solve now