Skip to main content

K partition with equal sum

Given the collection of positive integers. Our goal is to partition of that elements into K parts with equal sum. Let an example.

 collection[] = {6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15};
 k = 2

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :   6  2  7  1  5  9
 Set 2 :   8  4  3  15

 k = 4
 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :   6  2  7
 Set 2 :   1  5  9
 Set 3 :   8  4  3
 Set 4 :   15

 k = 3
 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :   6  2  7  1  4
 Set 2 :   8  3  9
 Set 3 :   5  15

Here given code implementation process.

// C Program 
// K partition with equal sum
#include <stdio.h>

// Find subset of given sum
int findSolution(int collection[], int result[], int visit[], int n, int k, int sum, int i, int j)
{
    if (i >= n || j >= k)
    {
        return 0;
    }
    if (sum == result[j])
    {
        if (j + 1 == k)
        {
            // When all subsets exist
            return 1;
        }
        else
        {
            // Backtrack next subset sum
            return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
        }
    }
    // Execute loop through by size n
    for (int x = i; x < n; ++x)
    {
        if (visit[x] == 0 && result[j] + collection[x] <= sum)
        {
            // Active visit status
            visit[x] = j + 1;
            result[j] = result[j] + collection[x];
            if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == 1)
            {
                // When solution is found
                return 1;
            }
            // Back to previous values
            result[j] = result[j] - collection[x];
            visit[x] = 0;
        }
    }
    return 0;
}
// Handles the request of partition of k with equal sum
void partition(int collection[], int n, int k)
{
    if (k <= 0 || k > n)
    {
        printf("\n Given %d partition not possible\n", k);
    }
    else
    {
        int i = 0;
        int j = 0;
        int sum = 0;
        // Sum of elements
        for (i = 0; i < n; ++i)
        {
            sum += collection[i];
        }
        if (sum % k == 0)
        {
            // When partition possible of equal sum
            // This is used to handle partition sum info
            int result[k];
            // This are used to track visited element
            int visit[n];
            // Through the loop set initial values 
            for (i = 0; i < n; ++i)
            {
                if (i < k)
                {
                    result[i] = 0;
                }
                visit[i] = 0;
            }
            if (findSolution(collection, result, visit, n, k, sum / k, 0, 0))
            {
                // Display calculated result
                printf("\n Total Sum : %d", sum);
                printf("\n Partition size : %d", k);
                printf("\n Equal sum is : %d", sum / k);
                printf("\n Output");
                printf("\n ------------------");
                // Display resultant set
                for (j = 1; j <= k; ++j)
                {
                    printf("\n Set %d : ", j);
                    for (i = 0; i < n; ++i)
                    {
                        if (visit[i] == j)
                        {
                            printf("  %d", collection[i]);
                        }
                    }
                }
                printf("\n\n");
            }
            else
            {
                printf("\n Partition of size %d cannot be divided into equal amount\n", k);
            }
        }
        else
        {
            printf("\n Partition with %d parts is not produce equal sum\n", k);
        }
    }
}
int main(int argc, char
    const *argv[])
{
    // Define collection of positive elements
    int collection[] = {
        6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
    };
    // Get the number of elements
    int n = sizeof(collection) / sizeof(collection[0]);
    // Test cases
    int k = 2;
    partition(collection, n, k);
    k = 4;
    partition(collection, n, k);
    k = 3;
    partition(collection, n, k);
    return 0;
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :   6  2  7  1  5  9
 Set 2 :   8  4  3  15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :   6  2  7
 Set 2 :   1  5  9
 Set 3 :   8  4  3
 Set 4 :   15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :   6  2  7  1  4
 Set 2 :   8  3  9
 Set 3 :   5  15
/*
  Java Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    public boolean findSolution(int[] collection, int[] result, int[] visit, int n, int k, int sum, int i, int j)
    {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result[j])
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        for (int x = i; x < n; ++x)
        {
            if (visit[x] == 0 && result[j] + collection[x] <= sum)
            {
                // Active visit status
                visit[x] = j + 1;
                result[j] = result[j] + collection[x];
                if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result[j] = result[j] - collection[x];
                visit[x] = 0;
            }
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    public void partition(int[] collection, int n, int k)
    {
        if (k <= 0 || k > n)
        {
            System.out.print("\n Given " + k + " partition not possible\n");
        }
        else
        {
            // Loop controlling variable i and j
            int i = 0;
            int j = 0;
            int sum = 0;
            // Sum of elements
            for (i = 0; i < n; ++i)
            {
                sum += collection[i];
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                int[] result = new int[k];
                // This are used to track visited element
                int[] visit = new int[n];
                // Through the loop set initial values 
                for (i = 0; i < n; ++i)
                {
                    if (i < k)
                    {
                        result[i] = 0;
                    }
                    visit[i] = 0;
                }
                if (findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
                {
                    // Display calculated result
                    System.out.print("\n Total Sum : " + sum + "");
                    System.out.print("\n Partition size : " + k + "");
                    System.out.print("\n Equal sum is : " + sum / k + "");
                    System.out.print("\n Output");
                    System.out.print("\n ------------------");
                    // Display resultant set
                    for (j = 1; j <= k; ++j)
                    {
                        System.out.print("\n Set " + j  + " : ");
                        for (i = 0; i < n; ++i)
                        {
                            if (visit[i] == j)
                            {
                                System.out.print(" " + collection[i]);
                            }
                        }
                    }
                    System.out.print("\n\n");
                }
                else
                {
                    System.out.print("\n Partition of size " + k + " cannot be divided into equal amount\n");
                }
            }
            else
            {
                System.out.print("\n Partition with " + k + " parts is not produce equal sum\n");
            }
        }
    }
    public static void main(String[] args)
    {
        Subset task = new Subset();
        // Define collection of positive elements
        int[] collection = {
            6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
        };
        // Get the number of elements
        int n = collection.length;
        // Test cases
        int k = 2;
        task.partition(collection, n, k);
        k = 4;
        task.partition(collection, n, k);
        k = 3;
        task.partition(collection, n, k);
    }
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  K partition with equal sum
*/
class Subset
{
    public:
        // Find subset of given sum
        bool findSolution(int collection[], int result[], int visit[], int n, int k, int sum, int i, int j)
        {
            if (i >= n || j >= k)
            {
                return false;
            }
            if (sum == result[j])
            {
                if (j + 1 == k)
                {
                    // When all subsets exist
                    return true;
                }
                else
                {
                    // Backtrack next subset sum
                    return this->findSolution(collection, result, visit, n, k, sum, 0, j + 1);
                }
            }
            // Execute loop through by size n
            for (int x = i; x < n; ++x)
            {
                if (visit[x] == 0 && result[j] + collection[x] <= sum)
                {
                    // Active visit status
                    visit[x] = j + 1;
                    result[j] = result[j] + collection[x];
                    if (this->findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                    {
                        // When solution is found
                        return true;
                    }
                    // Back to previous values
                    result[j] = result[j] - collection[x];
                    visit[x] = 0;
                }
            }
            return false;
        }
    // Handles the request of partition of k with equal sum
    void partition(int collection[], int n, int k)
    {
        if (k <= 0 || k > n)
        {
            cout << "\n Given " << k << " partition not possible\n";
        }
        else
        {
            // Loop controlling variable i and j
            int i = 0;
            int j = 0;
            int sum = 0;
            // Sum of elements
            for (i = 0; i < n; ++i)
            {
                sum += collection[i];
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                int result[k];
                // This are used to track visited element
                int visit[n];
                // Through the loop set initial values
                for (i = 0; i < n; ++i)
                {
                    if (i < k)
                    {
                        result[i] = 0;
                    }
                    visit[i] = 0;
                }
                if (this->findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
                {
                    // Display calculated result
                    cout << "\n Total Sum : " << sum << "";
                    cout << "\n Partition size : " << k << "";
                    cout << "\n Equal sum is : " << sum / k << "";
                    cout << "\n Output";
                    cout << "\n ------------------";
                    // Display resultant set
                    for (j = 1; j <= k; ++j)
                    {
                        cout << "\n Set " << j << " : ";
                        for (i = 0; i < n; ++i)
                        {
                            if (visit[i] == j)
                            {
                                cout << " " << collection[i];
                            }
                        }
                    }
                    cout << "\n\n";
                }
                else
                {
                    cout << "\n Partition of size " << k << " cannot be divided into equal amount\n";
                }
            }
            else
            {
                cout << "\n Partition with " << k << " parts is not produce equal sum\n";
            }
        }
    }
};
int main()
{
    Subset task = Subset();
    // Define collection of positive elements
    int collection[] = {
        6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
    };
    // Get the number of elements
    int n = sizeof(collection) / sizeof(collection[0]);
    // Test cases
    int k = 2;
    task.partition(collection, n, k);
    k = 4;
    task.partition(collection, n, k);
    k = 3;
    task.partition(collection, n, k);
    return 0;
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
// Include namespace system
using System;
/*
  C# Program for
  K partition with equal sum
*/
public class Subset
{
    // Find subset of given sum
    public Boolean findSolution(int[] collection, int[] result, int[] visit, int n, int k, int sum, int i, int j)
    {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result[j])
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        for (int x = i; x < n; ++x)
        {
            if (visit[x] == 0 && result[j] + collection[x] <= sum)
            {
                // Active visit status
                visit[x] = j + 1;
                result[j] = result[j] + collection[x];
                if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result[j] = result[j] - collection[x];
                visit[x] = 0;
            }
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    public void partition(int[] collection, int n, int k)
    {
        if (k <= 0 || k > n)
        {
            Console.Write("\n Given " + k + " partition not possible\n");
        }
        else
        {
            // Loop controlling variable i and j
            int i = 0;
            int j = 0;
            int sum = 0;
            // Sum of elements
            for (i = 0; i < n; ++i)
            {
                sum += collection[i];
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                int[] result = new int[k];
                // This are used to track visited element
                int[] visit = new int[n];
                // Through the loop set initial values
                for (i = 0; i < n; ++i)
                {
                    if (i < k)
                    {
                        result[i] = 0;
                    }
                    visit[i] = 0;
                }
                if (findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
                {
                    // Display calculated result
                    Console.Write("\n Total Sum : " + sum + "");
                    Console.Write("\n Partition size : " + k + "");
                    Console.Write("\n Equal sum is : " + sum / k + "");
                    Console.Write("\n Output");
                    Console.Write("\n ------------------");
                    // Display resultant set
                    for (j = 1; j <= k; ++j)
                    {
                        Console.Write("\n Set " + j + " : ");
                        for (i = 0; i < n; ++i)
                        {
                            if (visit[i] == j)
                            {
                                Console.Write(" " + collection[i]);
                            }
                        }
                    }
                    Console.Write("\n\n");
                }
                else
                {
                    Console.Write("\n Partition of size " + k + " cannot be divided into equal amount\n");
                }
            }
            else
            {
                Console.Write("\n Partition with " + k + " parts is not produce equal sum\n");
            }
        }
    }
    public static void Main(String[] args)
    {
        Subset task = new Subset();
        // Define collection of positive elements
        int[] collection = {
            6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
        };
        // Get the number of elements
        int n = collection.Length;
        // Test cases
        int k = 2;
        task.partition(collection, n, k);
        k = 4;
        task.partition(collection, n, k);
        k = 3;
        task.partition(collection, n, k);
    }
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
<?php
/*
  Php Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    public  function findSolution( & $collection, & $result, & $visit, $n, $k, $sum, $i, $j)
    {
        if ($i >= $n || $j >= $k)
        {
            return false;
        }
        if ($sum == $result[$j])
        {
            if ($j + 1 == $k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return $this->findSolution($collection, $result, $visit, $n, $k, $sum, 0, $j + 1);
            }
        }
        // Execute loop through by size n
        for ($x = $i; $x < $n; ++$x)
        {
            if ($visit[$x] == 0 && $result[$j] + $collection[$x] <= $sum)
            {
                // Active visit status
                $visit[$x] = $j + 1;
                $result[$j] = $result[$j] + $collection[$x];
                if ($this->findSolution($collection, $result, $visit, $n, $k, $sum, $i + 1, $j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                $result[$j] = $result[$j] - $collection[$x];
                $visit[$x] = 0;
            }
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    public  function partition( & $collection, $n, $k)
    {
        if ($k <= 0 || $k > $n)
        {
            echo "\n Given ". $k ." partition not possible\n";
        }
        else
        {
            // Loop controlling variable i and j
            $i = 0;
            $j = 0;
            $sum = 0;
            // Sum of elements
            for ($i = 0; $i < $n; ++$i)
            {
                $sum += $collection[$i];
            }
            if ($sum % $k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                $result = array_fill(0, $k, 0);
                // This are used to track visited element
                $visit = array_fill(0, $n, 0);
                if ($this->findSolution($collection, $result, $visit, $n, $k, intval($sum / $k), 0, 0) == true)
                {
                    // Display calculated result
                    echo "\n Total Sum : ". $sum ."";
                    echo "\n Partition size : ". $k ."";
                    echo "\n Equal sum is : ". intval($sum / $k) ."";
                    echo "\n Output";
                    echo "\n ------------------";
                    // Display resultant set
                    for ($j = 1; $j <= $k; ++$j)
                    {
                        echo "\n Set ". $j ." : ";
                        for ($i = 0; $i < $n; ++$i)
                        {
                            if ($visit[$i] == $j)
                            {
                                echo " ". $collection[$i];
                            }
                        }
                    }
                    echo "\n\n";
                }
                else
                {
                    echo "\n Partition of size ". $k ." cannot be divided into equal amount\n";
                }
            }
            else
            {
                echo "\n Partition with ". $k ." parts is not produce equal sum\n";
            }
        }
    }
}

function main()
{
    $task = new Subset();
    // Define collection of positive elements
    $collection = array(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
    // Get the number of elements
    $n = count($collection);
    // Test cases
    $k = 2;
    $task->partition($collection, $n, $k);
    $k = 4;
    $task->partition($collection, $n, $k);
    $k = 3;
    $task->partition($collection, $n, $k);
}
main();

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
/*
  Node Js Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    findSolution(collection, result, visit, n, k, sum, i, j)
    {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result[j])
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        for (var x = i; x < n; ++x)
        {
            if (visit[x] == 0 && result[j] + collection[x] <= sum)
            {
                // Active visit status
                visit[x] = j + 1;
                result[j] = result[j] + collection[x];
                if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result[j] = result[j] - collection[x];
                visit[x] = 0;
            }
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    partition(collection, n, k)
    {
        if (k <= 0 || k > n)
        {
            process.stdout.write("\n Given " + k + " partition not possible\n");
        }
        else
        {
            // Loop controlling variable i and j
            var i = 0;
            var j = 0;
            var sum = 0;
            // Sum of elements
            for (i = 0; i < n; ++i)
            {
                sum += collection[i];
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                var result = Array(k).fill(0);
                // This are used to track visited element
                var visit = Array(n).fill(0);
                if (this.findSolution(collection, result, visit, n, k, parseInt(sum / k), 0, 0) == true)
                {
                    // Display calculated result
                    process.stdout.write("\n Total Sum : " + sum + "");
                    process.stdout.write("\n Partition size : " + k + "");
                    process.stdout.write("\n Equal sum is : " + parseInt(sum / k) + "");
                    process.stdout.write("\n Output");
                    process.stdout.write("\n ------------------");
                    // Display resultant set
                    for (j = 1; j <= k; ++j)
                    {
                        process.stdout.write("\n Set " + j + " : ");
                        for (i = 0; i < n; ++i)
                        {
                            if (visit[i] == j)
                            {
                                process.stdout.write(" " + collection[i]);
                            }
                        }
                    }
                    process.stdout.write("\n\n");
                }
                else
                {
                    process.stdout.write("\n Partition of size " + k + " cannot be divided into equal amount\n");
                }
            }
            else
            {
                process.stdout.write("\n Partition with " + k + " parts is not produce equal sum\n");
            }
        }
    }
}

function main()
{
    var task = new Subset();
    // Define collection of positive elements
    var collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15];
    // Get the number of elements
    var n = collection.length;
    // Test cases
    var k = 2;
    task.partition(collection, n, k);
    k = 4;
    task.partition(collection, n, k);
    k = 3;
    task.partition(collection, n, k);
}
main();

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
#   Python 3 Program for
#   K partition with equal sum

class Subset :
    #  Find subset of given sum
    def findSolution(self, collection, result, visit, n, k, sum, i, j) :
        if (i >= n or j >= k) :
            return False
        
        if (sum == result[j]) :
            if (j + 1 == k) :
                #  When all subsets exist
                return True
            else :
                #  Backtrack next subset sum
                return self.findSolution(collection, result, visit, n, k, sum, 0, j + 1)
            
        
        #  Execute loop through by size n
        x = i
        while (x < n) :
            if (visit[x] == 0 and result[j] + collection[x] <= sum) :
                #  Active visit status
                visit[x] = j + 1
                result[j] = result[j] + collection[x]
                if (self.findSolution(collection, result, visit, n, k, sum, i + 1, j) == True) :
                    #  When solution is found
                    return True
                
                #  Back to previous values
                result[j] = result[j] - collection[x]
                visit[x] = 0
            
            x += 1
        
        return False
    
    #  Handles the request of partition of k with equal sum
    def partition(self, collection, n, k) :
        if (k <= 0 or k > n) :
            print("\n Given ", k ," partition not possible")
        else :
            #  Loop controlling variable i and j
            i = 0
            j = 0
            sum = 0
            #  Sum of elements
            while (i < n) :
                sum += collection[i]
                i += 1
            
            if (sum % k == 0) :
                #  When partition possible of equal sum
                #  This is used to handle partition sum info
                result = [0] * (k)
                #  This are used to track visited element
                visit = [0] * (n)
                if (self.findSolution(collection, result, visit, n, k, int(sum / k), 0, 0) == True) :
                    #  Display calculated result
                    print("\n Total Sum : ", sum ,"", end = "")
                    print("\n Partition size : ", k ,"", end = "")
                    print("\n Equal sum is : ", int(sum / k) ,"", end = "")
                    print("\n Output", end = "")
                    print("\n ------------------", end = "")
                    #  Display resultant set
                    j = 1
                    while (j <= k) :
                        print("\n Set ", j ," : ", end = "")
                        i = 0
                        while (i < n) :
                            if (visit[i] == j) :
                                print(" ", collection[i], end = "")
                            
                            i += 1
                        
                        j += 1
                    
                    print("\n")
                else :
                    print("\n Partition of size ", k ," cannot be divided into equal amount")
                
            else :
                print("\n Partition with ", k ," parts is not produce equal sum")
            
        
    

def main() :
    task = Subset()
    #  Define collection of positive elements
    collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15]
    #  Get the number of elements
    n = len(collection)
    #  Test cases
    k = 2
    task.partition(collection, n, k)
    k = 4
    task.partition(collection, n, k)
    k = 3
    task.partition(collection, n, k)

if __name__ == "__main__": main()

Output

 Total Sum :  60
 Partition size :  2
 Equal sum is :  30
 Output
 ------------------
 Set  1  :   6  2  7  1  5  9
 Set  2  :   8  4  3  15


 Total Sum :  60
 Partition size :  4
 Equal sum is :  15
 Output
 ------------------
 Set  1  :   6  2  7
 Set  2  :   1  5  9
 Set  3  :   8  4  3
 Set  4  :   15


 Total Sum :  60
 Partition size :  3
 Equal sum is :  20
 Output
 ------------------
 Set  1  :   6  2  7  1  4
 Set  2  :   8  3  9
 Set  3  :   5  15
#   Ruby Program for
#   K partition with equal sum

class Subset 
    #  Find subset of given sum
    def findSolution(collection, result, visit, n, k, sum, i, j) 
        if (i >= n || j >= k) 
            return false
        end

        if (sum == result[j]) 
            if (j + 1 == k) 
                #  When all subsets exist
                return true
            else 
                #  Backtrack next subset sum
                return self.findSolution(collection, result, visit, n, k, sum, 0, j + 1)
            end

        end

        #  Execute loop through by size n
        x = i
        while (x < n) 
            if (visit[x] == 0 && result[j] + collection[x] <= sum) 
                #  Active visit status
                visit[x] = j + 1
                result[j] = result[j] + collection[x]
                if (self.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true) 
                    #  When solution is found
                    return true
                end

                #  Back to previous values
                result[j] = result[j] - collection[x]
                visit[x] = 0
            end

            x += 1
        end

        return false
    end

    #  Handles the request of partition of k with equal sum
    def partition(collection, n, k) 
        if (k <= 0 || k > n) 
            print("\n Given ", k ," partition not possible\n")
        else 
            #  Loop controlling variable i and j
            i = 0
            j = 0
            sum = 0
            #  Sum of elements
            while (i < n) 
                sum += collection[i]
                i += 1
            end

            if (sum % k == 0) 
                #  When partition possible of equal sum
                #  This is used to handle partition sum info
                result = Array.new(k) {0}
                #  This are used to track visited element
                visit = Array.new(n) {0}
                if (self.findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true) 
                    #  Display calculated result
                    print("\n Total Sum : ", sum ,"")
                    print("\n Partition size : ", k ,"")
                    print("\n Equal sum is : ", sum / k ,"")
                    print("\n Output")
                    print("\n ------------------")
                    #  Display resultant set
                    j = 1
                    while (j <= k) 
                        print("\n Set ", j ," : ")
                        i = 0
                        while (i < n) 
                            if (visit[i] == j) 
                                print(" ", collection[i])
                            end

                            i += 1
                        end

                        j += 1
                    end

                    print("\n\n")
                else 
                    print("\n Partition of size ", k ," cannot be divided into equal amount\n")
                end

            else 
                print("\n Partition with ", k ," parts is not produce equal sum\n")
            end

        end

    end

end

def main() 
    task = Subset.new()
    #  Define collection of positive elements
    collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15]
    #  Get the number of elements
    n = collection.length
    #  Test cases
    k = 2
    task.partition(collection, n, k)
    k = 4
    task.partition(collection, n, k)
    k = 3
    task.partition(collection, n, k)
end

main()

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15

/*
  Scala Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    def findSolution(collection: Array[Int], result: Array[Int], visit: Array[Int], n: Int, k: Int, sum: Int, i: Int, j: Int): Boolean = {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result(j))
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        var x: Int = i;
        while (x < n)
        {
            if (visit(x) == 0 && result(j) + collection(x) <= sum)
            {
                // Active visit status
                visit(x) = j + 1;
                result(j) = result(j) + collection(x);
                if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result(j) = result(j) - collection(x);
                visit(x) = 0;
            }
            x += 1;
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    def partition(collection: Array[Int], n: Int, k: Int): Unit = {
        if (k <= 0 || k > n)
        {
            print("\n Given " + k + " partition not possible\n");
        }
        else
        {
            // Loop controlling variable i and j
            var i: Int = 0;
            var j: Int = 0;
            var sum: Int = 0;
            // Sum of elements
            while (i < n)
            {
                sum += collection(i);
                i += 1;
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                var result: Array[Int] = Array.fill[Int](k)(0);
                // This are used to track visited element
                var visit: Array[Int] = Array.fill[Int](n)(0);
                if (this.findSolution(collection, result, visit, n, k, (sum / k).toInt, 0, 0) == true)
                {
                    // Display calculated result
                    print("\n Total Sum : " + sum + "");
                    print("\n Partition size : " + k + "");
                    print("\n Equal sum is : " + (sum / k).toInt + "");
                    print("\n Output");
                    print("\n ------------------");
                    // Display resultant set
                    j = 1;
                    while (j <= k)
                    {
                        print("\n Set " + j + " : ");
                        i = 0;
                        while (i < n)
                        {
                            if (visit(i) == j)
                            {
                                print(" " + collection(i));
                            }
                            i += 1;
                        }
                        j += 1;
                    }
                    print("\n\n");
                }
                else
                {
                    print("\n Partition of size " + k + " cannot be divided into equal amount\n");
                }
            }
            else
            {
                print("\n Partition with " + k + " parts is not produce equal sum\n");
            }
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Subset = new Subset();
        // Define collection of positive elements
        var collection: Array[Int] = Array(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
        // Get the number of elements
        var n: Int = collection.length;
        // Test cases
        var k: Int = 2;
        task.partition(collection, n, k);
        k = 4;
        task.partition(collection, n, k);
        k = 3;
        task.partition(collection, n, k);
    }
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15
/*
  Swift 4 Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    func findSolution(_ collection: [Int], _ result: inout[Int], _ visit: inout[Int], _ n: Int, _ k: Int, _ sum: Int, _ i: Int, _ j: Int)->Bool
    {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result[j])
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return self.findSolution(collection, &result, &visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        var x: Int = i;
        while (x < n)
        {
            if (visit[x] == 0 && result[j] + collection[x] <= sum)
            {
                // Active visit status
                visit[x] = j + 1;
                result[j] = result[j] + collection[x];
                if (self.findSolution(collection, &result, &visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result[j] = result[j] - collection[x];
                visit[x] = 0;
            }
            x += 1;
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    func partition(_ collection: [Int], _ n: Int, _ k: Int)
    {
        if (k <= 0 || k > n)
        {
            print("\n Given ", k ," partition not possible");
        }
        else
        {
            // Loop controlling variable i and j
            var i: Int = 0;
            var j: Int = 0;
            var sum: Int = 0;
            // Sum of elements
            while (i < n)
            {
                sum += collection[i];
                i += 1;
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                var result: [Int] = Array(repeating: 0, count: k);
                // This are used to track visited element
                var visit: [Int] = Array(repeating: 0, count: n);
                if (self.findSolution(collection, &result, &visit, n, k, sum / k, 0, 0) == true)
                {
                    // Display calculated result
                    print("\n Total Sum : ", sum ,"", terminator: "");
                    print("\n Partition size : ", k ,"", terminator: "");
                    print("\n Equal sum is : ", sum / k ,"", terminator: "");
                    print("\n Output", terminator: "");
                    print("\n ------------------", terminator: "");
                    // Display resultant set
                    j = 1;
                    while (j <= k)
                    {
                        print("\n Set ", j ," : ", terminator: "");
                        i = 0;
                        while (i < n)
                        {
                            if (visit[i] == j)
                            {
                                print(" ", collection[i], terminator: "");
                            }
                            i += 1;
                        }
                        j += 1;
                    }
                    print("\n");
                }
                else
                {
                    print("\n Partition of size ", k ," cannot be divided into equal amount");
                }
            }
            else
            {
                print("\n Partition with ", k ," parts is not produce equal sum");
            }
        }
    }
}
func main()
{
    let task: Subset = Subset();
    // Define collection of positive elements
    let collection: [Int] = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15];
    // Get the number of elements
    let n: Int = collection.count;
    // Test cases
    var k: Int = 2;
    task.partition(collection, n, k);
    k = 4;
    task.partition(collection, n, k);
    k = 3;
    task.partition(collection, n, k);
}
main();

Output

 Total Sum :  60
 Partition size :  2
 Equal sum is :  30
 Output
 ------------------
 Set  1  :   6  2  7  1  5  9
 Set  2  :   8  4  3  15


 Total Sum :  60
 Partition size :  4
 Equal sum is :  15
 Output
 ------------------
 Set  1  :   6  2  7
 Set  2  :   1  5  9
 Set  3  :   8  4  3
 Set  4  :   15


 Total Sum :  60
 Partition size :  3
 Equal sum is :  20
 Output
 ------------------
 Set  1  :   6  2  7  1  4
 Set  2  :   8  3  9
 Set  3  :   5  15
/*
  Kotlin Program for
  K partition with equal sum
*/
class Subset
{
    // Find subset of given sum
    fun findSolution(collection: Array <Int> , result: Array <Int> , visit: Array <Int> , n: Int, k: Int, sum: Int, i: Int, j: Int): Boolean
    {
        if (i >= n || j >= k)
        {
            return false;
        }
        if (sum == result[j])
        {
            if (j + 1 == k)
            {
                // When all subsets exist
                return true;
            }
            else
            {
                // Backtrack next subset sum
                return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
            }
        }
        // Execute loop through by size n
        var x: Int = i;
        while (x < n)
        {
            if (visit[x] == 0 && result[j] + collection[x] <= sum)
            {
                // Active visit status
                visit[x] = j + 1;
                result[j] = result[j] + collection[x];
                if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
                {
                    // When solution is found
                    return true;
                }
                // Back to previous values
                result[j] = result[j] - collection[x];
                visit[x] = 0;
            }
            x += 1;
        }
        return false;
    }
    // Handles the request of partition of k with equal sum
    fun partition(collection: Array<Int> , n: Int, k: Int): Unit
    {
        if (k <= 0 || k > n)
        {
            print("\n Given " + k + " partition not possible\n");
        }
        else
        {
            // Loop controlling variable i and j
            var i: Int = 0;
            var j: Int ;
            var sum: Int = 0;
            // Sum of elements
            while (i < n)
            {
                sum += collection[i];
                i += 1;
            }
            if (sum % k == 0)
            {
                // When partition possible of equal sum
                // This is used to handle partition sum info
                var result: Array <Int> = Array(k)
                {
                    0
                };
                // This are used to track visited element
                var visit: Array<Int> = Array(n)
                {
                    0
                };
                if (this.findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
                {
                    // Display calculated result
                    print("\n Total Sum : " + sum + "");
                    print("\n Partition size : " + k + "");
                    print("\n Equal sum is : " + sum / k + "");
                    print("\n Output");
                    print("\n ------------------");
                    // Display resultant set
                    j = 1;
                    while (j <= k)
                    {
                        print("\n Set " + j + " : ");
                        i = 0;
                        while (i < n)
                        {
                            if (visit[i] == j)
                            {
                                print(" " + collection[i]);
                            }
                            i += 1;
                        }
                        j += 1;
                    }
                    print("\n\n");
                }
                else
                {
                    print("\n Partition of size " + k + " cannot be divided into equal amount\n");
                }
            }
            else
            {
                print("\n Partition with " + k + " parts is not produce equal sum\n");
            }
        }
    }
}
fun main(args: Array <String> ): Unit
{
    var task: Subset = Subset();
    // Define collection of positive elements
    var collection: Array<Int> = arrayOf(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
    // Get the number of elements
    var n: Int = collection.count();
    // Test cases
    var k: Int = 2;
    task.partition(collection, n, k);
    k = 4;
    task.partition(collection, n, k);
    k = 3;
    task.partition(collection, n, k);
}

Output

 Total Sum : 60
 Partition size : 2
 Equal sum is : 30
 Output
 ------------------
 Set 1 :  6 2 7 1 5 9
 Set 2 :  8 4 3 15


 Total Sum : 60
 Partition size : 4
 Equal sum is : 15
 Output
 ------------------
 Set 1 :  6 2 7
 Set 2 :  1 5 9
 Set 3 :  8 4 3
 Set 4 :  15


 Total Sum : 60
 Partition size : 3
 Equal sum is : 20
 Output
 ------------------
 Set 1 :  6 2 7 1 4
 Set 2 :  8 3 9
 Set 3 :  5 15




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment