3 Partition Problem - C++ Solution

1. Introduction

In this blog post, we explore the 3-partition problem, a classic problem in combinatorial optimization. The challenge is to determine whether a given set of positive integers can be partitioned into three subsets with equal sums.

Problem

Given a set S of positive integers, the task is to find out if S can be partitioned into three disjoint subsets that all have the same sum and collectively cover S.

Example:

Input: S = [7, 3, 2, 1, 5, 4, 8]

Output: true

Explanation: S can be partitioned into three partitions [[7, 3], [5, 4, 1], [8, 2]], each having a sum of 10.

2. Solution Steps

1. Calculate the total sum of the set. If it's not divisible by 3, return false.

2. Use a recursive approach to check if a partition with a third of the total sum can be made three times.

3. Track the elements already used in a partition to avoid repetition.

4. Return true if three valid partitions are found; otherwise, return false.

3. Code Program

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

bool canPartition(vector<int>& nums, int n, int sum, vector<bool>& taken) {
    if (sum == 0) return true;

    if (n == 0) return false;

    // Try including the last element in the partition
    if (nums[n - 1] <= sum) {
        taken[n - 1] = true;
        if (canPartition(nums, n - 1, sum - nums[n - 1], taken)) return true;
        taken[n - 1] = false; // Backtrack
    }

    // Or exclude it and move to the next element
    return canPartition(nums, n - 1, sum, taken);
}

bool partition3(vector<int>& nums) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);

    if (totalSum % 3 != 0) return false;

    vector<bool> taken(nums.size(), false);

    // Try forming the first partition
    if (!canPartition(nums, nums.size(), totalSum / 3, taken)) return false;

    // Try forming the second partition
    if (!canPartition(nums, nums.size(), totalSum / 3, taken)) return false;

    // If two partitions are formed, the third is automatically formed
    return true;
}

int main() {
    vector<int> nums = {7, 3, 2, 1, 5, 4, 8};
    cout << "Can be partitioned into 3 subsets with equal sum: " << boolalpha << partition3(nums) << endl;
    return 0;
}

Output:

Can be partitioned into 3 subsets with equal sum: true

Explanation:

The partition3 function first checks if the total sum of the set is divisible by 3. It then uses a helper function canPartition, which attempts to create a partition with a sum equal to a third of the total sum. This function uses recursion and backtracking to try including or excluding each element. If two such partitions are successfully formed, the remaining elements automatically form the third partition, indicating that the set can be divided into three subsets with equal sums.