Partition Problem - C++ Solution

1. Introduction

In this blog post, we tackle the Partition Problem, a classic problem in computer science and dynamic programming. The challenge is to determine whether a given set of positive integers can be divided into two subsets with equal sums.

Problem

Given a set of positive integers, the task is to check if the set can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example:

Input: S = [3, 1, 1, 2, 2, 1]

Output: true

Explanation: The set can be partitioned into two subsets, each having a sum of 5.

2. Solution Steps

1. Calculate the total sum of the set. If it is odd, return false since an odd sum cannot be split into two equal parts.

2. Use dynamic programming to find if there is a subset with a sum equal to half of the total sum.

3. Initialize a table to keep track of possible sums.

4. Fill the table iteratively, considering each element and updating the table for possible sums.

5. The answer will be in the cell representing half the total sum.

3. Code Program

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

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

    if (totalSum % 2 != 0) return false; // Odd sum cannot be split into two equal parts

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

    // Initialize the first column as true since sum of 0 is always possible
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // Fill the DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= halfSum; 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];
            }
        }
    }

    return dp[n][halfSum];
}

int main() {
    vector<int> S = {3, 1, 1, 2, 2, 1};
    cout << "Can be partitioned into two subsets with equal sum: " << boolalpha << canPartition(S) << endl;
    return 0;
}

Output:

Can be partitioned into two subsets with equal sum: true

Explanation:

The canPartition function first checks if the total sum of the set is odd. If so, it returns false as it's impossible to split an odd sum into two equal parts. It then uses dynamic programming to determine if a subset with a sum equal to half of the total sum exists. The DP table dp is filled iteratively, where dp[i][j] represents whether a sum j can be achieved with the first i numbers. The final cell dp[n][halfSum] gives the answer, indicating whether the set can be partitioned into two subsets with equal sums. This approach efficiently solves the partition problem, as demonstrated in the output for the given example.