 Explore
Placement Prep Edit Edit

# Minimum sum partition problem using dynamic programming | FACE Prep

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

## Algorithm for the minimum sum partition problem

• 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.

## Program for the minimum sum partition problem

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  