Minimum Sum Partition Problem - C++ Solution

1. Introduction

This blog post explores the Minimum Sum Partition Problem, a classic problem in dynamic programming. The challenge is to partition a set of positive integers into two subsets such that the absolute difference between their sums is minimized.

Problem

Given a set S of positive integers, the task is to partition it into two subsets, S1 and S2, such that the difference between the sum of elements in S1 and S2 is as small as possible. The solution should return the minimum absolute difference between the sums of the two partitions.

Examples:

- Input: S = [10, 20, 15, 5, 25]

Output: 5

- Input: []

Output: 0

2. Solution Steps

1. Calculate the total sum of the set S.

2. Use dynamic programming to find the subset with a sum that is as close as possible to half of the total sum.

3. The minimum difference will be twice the difference between the total sum and twice the subset sum found in step 2.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPartitionDifference(vector<int>& nums) {
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }

    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(totalSum / 2 + 1, false));

    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= totalSum / 2; j++) {
            if (nums[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    int minDiff = totalSum;
    for (int j = totalSum / 2; j >= 0; j--) {
        if (dp[n][j]) {
            minDiff = totalSum - 2 * j;
            break;
        }
    }

    return minDiff;
}

int main() {
    vector<int> S = {10, 20, 15, 5, 25};
    cout << "Minimum sum partition difference: " << minPartitionDifference(S) << endl;
    return 0;
}

Output:

Minimum sum partition difference: 5

Explanation:

The minPartitionDifference function calculates the total sum of the set S and initializes a dynamic programming table dp. It then fills dp to find the largest sum less than or equal to half of the total sum that can be formed with the elements of S. The minimum difference is calculated as the difference between the total sum and twice the subset sum found. This approach efficiently finds the minimum absolute difference between the sums of two partitions, as demonstrated in the output for the given example.