Minimum Sum Partition — Day 47(Python)

Image for post
Image for post
Photo by Maria Teneva on Unsplash

Today, we will be looking into another Dynamic Programming question. The problem statement is a variation of the Knapsack problem. Let us look into the problem statement. I used Aditya Verma’s video as a reference to solve this problem. I have included the link to his video at the end of the video.

Partition a set into two subsets such that the difference of subset sums is minimum

Given an integer array arr of size N, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

Example 1:

Input: N = 4, arr[] = {1, 6, 11, 5} 
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11

Example 2:

Input: N = 2, arr[] = {1, 4}
Output: 3
Explanation:
Subset1 = {1}, sum of Subset1 = 1
Subset2 = {4}, sum of Subset2 = 4

Your Task:
You don’t need to read input or print anything. Complete the function minDifference() which takes N and array arr as input parameters and returns the integer value

Expected Time Complexity: O(N*|sum of array elements|)
Expected Auxiliary Space: O(N*|sum of array elements|)

Constraints:
1 ≤ N*|sum of array elements| ≤ 106

I mentioned in the introduction that the Minimum sum partition problem can be solved using the logic of the knapsack problem. We will have to perform some pre-processing before using the knapsack logic.

Let us take an example to understand the algorithm.

Input: N = 4, arr[] = {1, 2, 3, 5}

We need to divide the above array into two parts, such that the difference between the sum of this individual sub-array is minimum.

Image for post
Image for post

We will be taking the absolute difference between the sum of two sub-arrays since we would not know in prior which sub-array has the higher sum. Next, we need to understand that the range of our difference will range between 0 to the sum of the total array. If one of the sub-array is empty, the other one will have all the numbers hence the difference will the total sum of the array. If the subarray can be partitioned in such a way that both the arrays add up to the same value, then the difference will be 0.

Image for post
Image for post

Wait! Do we have to find the total values of both the subarray? Can we just find the sum of just one subarray and then subtract this value from the total of the whole array?

Let us look at the below example.

Image for post
Image for post

We now understood the fact that we are required to find the sum of only one sub-array. At present, we know 2 points.

  1. The range in which the difference can fall i.e. between 0 and the sum of the array.
  2. The point that we need to find the sum of sub-array such that it falls within this range.

This reminds of partition equal sum subset, with a difference that this time we will find subarray sum until the sum reaches the total array sum. I will be directly writing the solution for the dynamic programming part, as I have already explained logical flow before. Incase you need a refresher, kindly follow this link.

def minDiffernce(arr, n):
total_sum = sum(arr)
memo = [[False for j in range((total_sum)+1)]for i in range(n+1)]
for i in range(len(memo)):
memo[i][0] = True
for i in range(1, len(memo)):
for j in range(1,len(memo[0])):
if arr[i-1] <= j:
memo[i][j] = memo[i-1][j-arr[i-1]] or memo[i-1][j]
else:
memo[i][j] = memo[i-1][j]

Recall the column signifies the maximum sum that can be obtained and the rows represent the numbers of elements in the array. To solve the given problem, we need only the last row as we need all the numbers from our list.

Before we move ahead, we need to understand some Math.

Our question wants us to minimize( S2 - S1)

We know that,

Total sum = S1 + S2

Therefore,

Total sum - S1 = S2

Substitute value of S2 in minimization equation.

min(Total sum - S1 - S1)

min(Total sum - 2 * S1)

The above calculations says that sum of one of the subarray will be within the half of total sum of the whole array. Hence we need not calculate the memoization table for the total sum of the array. We will be calculating the sum only until the half of the total sum. Let us bring that change in our code.

def minDiffernce(arr, n):
total_sum = sum(arr)
memo = [[False for j in range((total_sum//2)+1)]for i in range(n+1)]
for i in range(len(memo)):
memo[i][0] = True
for i in range(1, len(memo)):
for j in range(1,len(memo[0])):
if arr[i-1] <= j:
memo[i][j] = memo[i-1][j-arr[i-1]] or memo[i-1][j]
else:
memo[i][j] = memo[i-1][j]

Next, we will take the last row from the memo table. As mentioned earlier, the column represent the total sum, each cell represent if the column number can be obtained using numbers from the list. We are concerned with only the last row, since we want all numbers from the list as part of partition.

Recall the math calculation, we need to minimize the following equation,

min(Total sum — 2 * S1)

Take those columns numbers that are marked as True, this will be S1. Subtract the double of this value from the total sum. The minimum value among these obtained numbers is the final answer.

Let us look into the code snippet.

class Solution:
def minDiffernce(self, arr, n):
total_sum = sum(arr)
memo = [[False for j in range((total_sum//2)+1)]for i in range(n+1)]
for i in range(len(memo)):
memo[i][0] = True
for i in range(1, len(memo)):
for j in range(1,len(memo[0])):
if arr[i-1] <= j:
memo[i][j] = memo[i-1][j-arr[i-1]] or memo[i-1][j]
else:
memo[i][j] = memo[i-1][j]

min_diff = float('inf')
for i in range(len(memo[0])):
if memo[-1][i]:
min_diff = min(min_diff, abs(total_sum-(2*i)))
return min_diff

Another optimization that can be made is starting the loop from the end of selected last row, take the first True cell value that we get and return total sum — 2* the column value.

class Solution:
def minDiffernce(self, arr, n):
total_sum = sum(arr)
memo = [[False for j in range((total_sum//2)+1)]for i in range(n+1)]
for i in range(len(memo)):
memo[i][0] = True
for i in range(1, len(memo)):
for j in range(1,len(memo[0])):
if arr[i-1] <= j:
memo[i][j] = memo[i-1][j-arr[i-1]] or memo[i-1][j]
else:
memo[i][j] = memo[i-1][j]

min_diff = float('inf')
for i in range(len(memo[0])-1, -1, -1):
if memo[-1][i]:
min_diff = min(min_diff, abs(total_sum-(2*i)))
return min_diff

Complexity analysis.

Time Complexity

We are creating a 2D array of size ((N)*(H)) and traversing through the entire table once. Hence the time complexity is ((N)*(H)), where N is the count of numbers in the array and H is half the sum of numbers in the array.

Space Complexity.

We are creating a 2D array of size ((N)*(H)), hence the space complexity is ((N)*(H)), where N is the count of numbers in the array and H is half the sum of numbers in the array.

I have used Aditya Verma’s video as a reference to solve this problem.

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store