Thursday, January 17, 2019

Minimum Sum Partition Problem

Statement: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

Geeksforgeeks problem link : https://practice.geeksforgeeks.org/problems/minimum-sum-partition/0

Solution Explanation:

Simple recursive solution might be :

From index 0 start including each element into either of the partitions and recurse for the next index.
This is exponential complexity O(2^n)

What we can do is start from index 0. We either include it in first or second partition. For next index in the function call we include weight of first and second partition. When it reaches the end index it has a certain first partition and second partition sum and returns the difference between them. The indices previous to this receive the difference as return value and check to see if including the current index to the first or second partition gives overall less difference at the last index, given the current weight supplied by previous index.

A particular function call state is defined by the sum of first/second partition elements and the index we are seeing.

solve(int index, int firstPartitionSum, int secondPartitionSum)

DP[Index][FirstPartitionSum]

Code:



No comments:

Post a Comment