Horje
Partition Equal Subset Sum in C

Partition Equal Subset Sum problem involves dividing a given set into k subsets such that the sum of elements in each subset is the same. In this article, we will learn the solution to this problem in C programming language.

Example:

Given an array of integers and a number k, determine if it is possible to partition the array into k subsets such that the sum of elements in each subset is equal.

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}

Partitioning Equal Subset Sum in C Language

We can solve this problem recursively by maintaining an array for the sum of each partition and a boolean array to check whether an element is already included in some partition.

Approach:

  • Check Base Cases
    • If k is 1, return true since the whole array is one subset.
    • If the number of elements N is less than k, return false since we can’t partition the array into more subsets than there are elements.
    • Calculate the total sum of the array. If the sum is not divisible by k, return false.:
  • Initialize Variables:
    • Calculate the target sum for each subset as total_sum / k.
    • Create an array subsetSum to store the sum of each subset.
    • Create a boolean array taken to track whether an element is included in any subset.
  • Recursive Function:
    • Use a recursive helper function to try to add each element to a subset.
    • If the sum of a subset reaches the target sum, recursively check for the next subset.
    • If k-1 subsets reach the required sum, the remaining elements must form the last subset.


C Program for Partitioning into K Equal Subsets Sum

The below is the implementation of the above approach for solving partioning equal subset sum problem in C.

C 
// C program to solve Partitioning Equal Subset Sum

#include <stdbool.h>
#include <stdio.h>

// Recursive utility method to check K equal sum partition
// of array
bool isKPartitionPossibleRec(int arr[], int subsetSum[],
                             bool taken[], int subset,
                             int K, int N, int curIdx,
                             int limitIdx)
{
    // If the current subset sum equals the target subset
    // sum
    if (subsetSum[curIdx] == subset) {
        // If K-1 subsets are formed, the last subset is
        // also formed
        if (curIdx == K - 2)
            return true;

        // Recursive call for the next subset
        return isKPartitionPossibleRec(arr, subsetSum,
                                       taken, subset, K, N,
                                       curIdx + 1, N - 1);
    }

    // Try to include elements in the current partition
    for (int i = limitIdx; i >= 0; i--) {
        // Skip if the element is already taken
        if (taken[i])
            continue;

        // Calculate the new subset sum if the current
        // element is included
        int tmp = subsetSum[curIdx] + arr[i];
        // If the new subset sum does not exceed the target
        if (tmp <= subset) {
            // Mark the element as taken
            taken[i] = true;
            // Add the element to the current subset sum
            subsetSum[curIdx] += arr[i];

            // Recursively check the next element
            bool next = isKPartitionPossibleRec(
                arr, subsetSum, taken, subset, K, N, curIdx,
                i - 1);
            // Backtrack: unmark the element
            taken[i] = false;
            // Backtrack: remove the element from the
            // current subset sum
            subsetSum[curIdx] -= arr[i];
            // If a valid partition is found, return true
            if (next)
                return true;
        }
    }
    // Return false if no valid partition is found
    return false;
}

// Method returns true if arr can be partitioned into K
// subsets with equal sum
bool isKPartitionPossible(int arr[], int N, int K)
{
    if (K == 1)
        // Only one partition is always possible
        return true;

    if (N < K)
        // Not enough elements to partition into K subsets
        return false;

    int sum = 0;
    for (int i = 0; i < N; i++)
        // Calculate the total sum of the array
        sum += arr[i];
    if (sum % K != 0)
        // If the total sum is not divisible by K,
        // partitioning is not possible

        return false;
    // Target subset sum
    int subset = sum / K;
    // Array to store the sum of each subset
    int subsetSum[K];
    // Array to keep track of taken elements
    bool taken[N];

    for (int i = 0; i < K; i++)
        // Initialize subset sums to 0
        subsetSum[i] = 0;

    for (int i = 0; i < N; i++)
        // Initialize all elements as not taken
        taken[i] = false;
    // Initialize the first subset sum with the last element
    subsetSum[0] = arr[N - 1];
    // Mark the last element as taken
    taken[N - 1] = true;

    // Start the recursive utility function
    return isKPartitionPossibleRec(arr, subsetSum, taken,
                                   subset, K, N, 0, N - 1);
}

int main()
{
    // Initialize an array
    int arr[] = { 2, 1, 4, 5, 3, 3 };
    // Calculate the size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;

    // If partition is possible, print it
    if (isKPartitionPossible(arr, N, K))
        printf("Partitions into equal sum is possible.\n");
    // If partition is not possible, print this
    else
        printf(
            "Partitions into equal sum is not possible.\n");

    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.
Space Complexity: O(N), Extra space is required for visited array.


 


Reffered: https://www.geeksforgeeks.org

C Language

Related
Shortest Path Algorithm in C Shortest Path Algorithm in C
Graph Cycle Detection in C Graph Cycle Detection in C
Longest Increasing Subsequence in C Longest Increasing Subsequence in C
How to Create a Static Library in C? How to Create a Static Library in C?
C Program to Implement Binomial Heap C Program to Implement Binomial Heap

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



 

Horje