Link copied to clipboard. Share away!

Dismiss

Published on 11 Mar 2020

Minimum sum partition problem using dynamic programming is discussed here. Given a set of integers, partition the set such the difference between the two set is minimum (absolute difference ) and print the difference.

**Sample Input:**

4 (number of elements of the array)

14 25 78 96 (array elements)

**Sample Output:**

7

**Explanation:**

S1 = {96, 14}

S2 = {78, 25}

Sum of S1 = 110

Sum of S2 = 103

|S1 - S2| = 7

- Divide the set into two parts.
- Consider the following factors while partitioning it.
- Let dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum equal to j 0 otherwise}
- Repeat from i = 1 to n
- Repeat from j = 1 to sum of all elements
- So, dp[n+1][sum+1] will be 1 if
- Sum j is achieved including the i'th item
- Sum j is achieved excluding the i'th item.
- Let the sum of all the elements be S.
- To find Minimum sum difference, w have to find j such that Min {sum - j*2 : dp[n][j] == 1 } where j varies from 0 to sum/2
- The idea is, the sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.

C++

Output

Input -
5
5 7 3 1 9
Output -
1

**Test Case 1**

I/P

5

5 7 3 1 9

O/P

1

**Test Case 2**

I/P

4

14 25 78 96

O/P

7

**Test Case 3**

I/P

7

45 63 52 41 89 75 65

O/P

18

**Test Case 4**

I/P

6

14 25 78 96 32 10

O/P

13

**Test Case 5**

I/P

6

2 2 2 2 2 2

O/P

0

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×