Horje
Partition Equal Subset Sum in C++

Partition Equal Subset Sum problem is a classic problem in which we have to find whether a given set of positive integers can be partitioned into two subsets such that the sum of the elements in both subsets is equal. In this article, we will learn the solution to this problem in C++ programming language.

Example:

Input:
arr[] = {2, 1, 4, 5, 3, 3}
k = 3

Output:
Partitions into equal sum is possible.

Explanation: The array can be partitioned into 3 subsets with equal sum: {2, 4}, {1, 5}, {3, 3}

Methods to Find Partition Equal Subset Sum in C++ Language

Method 1: Recursive Approach

In the recursive approach, we explore all possible subsets and check if there exists any partition with subsets having equal sums. If the total sum is not divisible by k, it is impossible to partition the array into k equal subsets.

Approach:

  • Calculate the total sum of the array. If it is not divisible by k, return false.
  • Recursively explore all subsets to check if there are k subsets with a sum equal to total_sum/k.

Below is the implementation of the above approach:

C++ 
// C++ program to partition an array into K subsets with
// equal sum

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

// Helper function to check if we can partition the array
// into K subsets
bool canPartitionKSubsetsUtil(vector<int>& nums,
                              vector<bool>& visited,
                              int start_index, int k,
                              int cur_sum, int target_sum)
{
    if (k == 1)
        // Only one partition left, so the remaining
        // elements must form the last subset
        return true;

    if (cur_sum == target_sum)
        // Current partition is done, move on to the next
        // partition
        return canPartitionKSubsetsUtil(
            nums, visited, 0, k - 1, 0, target_sum);

    // Try including each number in the current partition
    for (int i = start_index; i < nums.size(); i++) {
        if (!visited[i]
            && cur_sum + nums[i] <= target_sum) {
            // Mark the number as visited
            visited[i] = true;
            // Recursively try to form the partition
            // including the current number
            if (canPartitionKSubsetsUtil(
                    nums, visited, i + 1, k,
                    cur_sum + nums[i], target_sum))
                return true;
            // Backtrack
            visited[i] = false;
        }
    }
    // Partitioning is not possible with the current
    // configuration
    return false;
}

// Function to check if the array can be partitioned into K
// subsets with equal sum
bool canPartitionKSubsets(vector<int>& nums, int k)
{
    // Calculate the total sum of the array
    int total_sum = accumulate(nums.begin(), nums.end(), 0);
    if (total_sum % k != 0)
        // If total sum is not divisible by k, partitioning
        // is not possible
        return false;
    // Keep track of visited elements
    vector<bool> visited(nums.size(), false);
    // Start the partitioning process
    return canPartitionKSubsetsUtil(nums, visited, 0, k, 0,
                                    total_sum / k);
}

int main()
{
    vector<int> arr = { 2, 1, 4, 5, 3, 3 };
    int k = 3;
    // Check if partitioning into equal sum subsets is
    // possible
    if (canPartitionKSubsets(arr, k))
        cout << "Partitions into equal sum is possible."
             << endl;
    else
        cout << "Partitions into equal sum is not possible."
             << endl;
    return 0;
}

Output
Partitions into equal sum is possible.

Time Complexity: O(2^(N * K)), Because if we have K trees stacked on top of each other, the new height of the tree is K * n. i.e one subset is not independent from other.
Auxiliary Space: O(N), Extra space is required for visited array.

Method 2: Dynamic Programming Approach

The dynamic programming approach optimizes the recursive solution by storing the results of subproblems to avoid redundant calculations. We use a bitmask to represent the inclusion of elements in subsets and a DP array to store the sum of subsets.

Approach:

  • Calculate the total sum of the array. If it is not divisible by k, return false.
  • Use a DP array and bitmask to keep track of the sum of subsets.
  • Iterate through the array, updating the DP array to reflect possible subset sums.

Below is the implementation of the above approach:

C++ 
// C++ program to partition an array into K subsets with
// equal sum using dynamic programming and bitmasking

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

// Function to check if the array can be partitioned into K
// subsets with equal sum
bool canPartitionKSubsets(vector<int>& nums, int k)
{
    // Calculate the total sum of the array
    int total_sum = accumulate(nums.begin(), nums.end(), 0);

    // If total sum is not divisible by k, partitioning is
    // not possible
    if (total_sum % k != 0)
        return false;
    // Calculate the target sum for each subset
    int target_sum = total_sum / k;
    // Initialize the dp array
    vector<int> dp(1 << nums.size(), -1);
    // Base case: no elements taken, sum is 0
    dp[0] = 0;

    // Iterate over all possible subsets using bitmasking
    for (int mask = 0; mask < (1 << nums.size()); mask++) {
        if (dp[mask] == -1)
            // Skip invalid subsets
            continue;

        // Try adding each element to the current subset
        for (int i = 0; i < nums.size(); i++) {
            if (!(mask & (1 << i))
                && dp[mask] + nums[i] <= target_sum) {
                dp[mask | (1 << i)]
                    = (dp[mask] + nums[i]) % target_sum;
            }
        }
    }

    // Check if all elements can be partitioned into k
    // subsets with equal sum
    return dp[(1 << nums.size()) - 1] == 0;
}

int main()
{
    // Array to be partitioned
    vector<int> arr = { 2, 1, 4, 5, 3, 3 };
    // Number of subsets
    int k = 3;

    // Check if partitioning into equal sum subsets is
    // possible
    if (canPartitionKSubsets(arr, k))
        cout << "Partitions into equal sum is possible."
             << endl;
    else
        cout << "Partitions into equal sum is not possible."
             << endl;

    return 0;
}

Output
Partitions into equal sum is possible.

Time Complexity: O(K * 2^N)
Auxiliary Space: O(2^N)

Method 3: Space Optimized Dynamic Programming

In this approach, we optimize the space complexity of the dynamic programming solution by using a 1D DP array instead of a 2D array. This reduction is possible because we only need the current and previous states to compute the solution.

Approach:

  • Calculate the total sum of the array. If it is not divisible by k, return false.
  • Use a 1D DP array to store results of subproblems.
  • Iterate through the array, updating the DP array to reflect possible subset sums.

Below is the implementation of the above approach:

C++ 
// C++ program to partition an array into K subsets with
// equal sum using dynamic programming and bitmasking

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

// Function to check if the array can be partitioned into K
// subsets with equal sum
bool canPartitionKSubsets(vector<int>& nums, int k)
{
    // Calculate the total sum of the array
    int total_sum = accumulate(nums.begin(), nums.end(), 0);

    // If total sum is not divisible by k, partitioning is
    // not possible
    if (total_sum % k != 0)
        return false;

    // Calculate the target sum for each subset
    int target_sum = total_sum / k;

    // Initialize the dp array with -1
    vector<int> dp(1 << nums.size(), -1);

    // Base case: no elements taken, sum is 0
    dp[0] = 0;

    // Iterate over all possible subsets using bitmasking
    for (int mask = 0; mask < (1 << nums.size()); mask++) {
        // Skip invalid subsets
        if (dp[mask] == -1)
            continue;

        // Try adding each element to the current subset
        for (int i = 0; i < nums.size(); i++) {
            // Check if the element is not already in the
            // subset and if adding it does not exceed the
            // target sum
            if (!(mask & (1 << i))
                && dp[mask] + nums[i] <= target_sum) {
                // Update the dp array with the new subset
                dp[mask | (1 << i)]
                    = (dp[mask] + nums[i]) % target_sum;
            }
        }
    }

    // Check if all elements can be partitioned into k
    // subsets with equal sum
    return dp[(1 << nums.size()) - 1] == 0;
}

int main()
{
    // Array to be partitioned
    vector<int> arr = { 2, 1, 4, 5, 3, 3 };

    // Number of subsets
    int k = 3;

    // Check if partitioning into equal sum subsets is
    // possible
    if (canPartitionKSubsets(arr, k))
        cout << "Partitions into equal sum is possible."
             << endl;
    else
        cout << "Partitions into equal sum is not possible."
             << endl;

    return 0;
}

Output
Partitions into equal sum is possible.

Time Complexity: O(K * 2^N)
Auxiliary Space: O(2^N)


 


Reffered: https://www.geeksforgeeks.org

C++

Related
Function Overloading vs Function Templates in C++ Function Overloading vs Function Templates in C++
Edit Distance in C++ Edit Distance in C++
Why Can&#039;t We Declare a std::vector&lt;AbstractClass&gt; in C++? Why Can&#039;t We Declare a std::vector&lt;AbstractClass&gt; in C++?
What Requirements Must std::map Key Classes Meet to be Valid Keys? What Requirements Must std::map Key Classes Meet to be Valid Keys?
C++ 03 Standard C++ 03 Standard

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 21



 

Horje