# Number of ways to partition a set into k subsets

In this problem, we are tasked with finding the number of ways to partition a set of n elements into k non-empty subsets. The objective is to determine how many different ways we can distribute the elements into these subsets.

## Problem Statement

Given a set of n elements and a positive integer k, we need to find the number of distinct ways to partition the set into k non-empty subsets.

## Example Scenario

Let's say we have a set of 6 elements: {1, 2, 3, 4, 5, 6}. If we want to partition this set into 3 subsets, the total number of ways to do so is 90.

## Idea to Solve the Problem

To solve this problem, we can use dynamic programming with memoization. We'll define a recursive function that calculates the number of ways to partition the set into k subsets. We'll consider two cases for each element: either it's included in a subset or it's not.

## Pseudocode

``````int partition(int n, int k)
{
// Base cases
if (n == 0 || k == 0 || k > n)
return 0;
if (k == 1 || k == n)
return 1;

// Recursive cases
return partition(n - 1, k - 1) + k * partition(n - 1, k);
}``````

## Algorithm Explanation

1. Create a function `partition` that takes two arguments: `n` (number of elements in the set) and `k` (number of subsets).
2. Implement base cases:
• If `n` is 0, `k` is 0, or `k` is greater than `n`, return 0 (invalid cases).
• If `k` is 1 or `k` is equal to `n`, return 1 (only one way to partition in these cases).
3. Implement recursive cases:
• For each element in the set, calculate the number of ways to partition the remaining elements into `k - 1` subsets, considering that the current element is included in one of the subsets.
• Calculate the number of ways to partition the remaining elements into `k` subsets, considering that the current element is not included in any subset.
• Add the results of these two recursive calls.

## Program Solution

``````// C program
// Number of ways to partition a set into k subsets
#include <stdio.h>

int partition(int n, int k)
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return partition(n - 1, k - 1) + k * partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
void countPartition(int n, int k)
{
// Display given data
printf("\n Given n : %d", n);
printf("\n Given k : %d", k);
// Display calculated result
printf("\n Total partition  : %d", partition(n, k));
}
int main(int argc, char
const *argv[])
{
// Test cases
countPartition(6, 3);
countPartition(5, 2);
return 0;
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition  : 90
Given n : 5
Given k : 2
Total partition  : 15``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Treap implementation
*/
class SubsetsPartition
{
public: int partition(int n, int k)
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return this->partition(n - 1, k - 1) + k *this->partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
void countPartition(int n, int k)
{
// Display given data
cout << "\n Given n : " << n;
cout << "\n Given k : " << k;
// Display calculated result
cout << "\n Total partition : " << this->partition(n, k);
}
};
int main()
{
// Test cases
return 0;
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````package main
import "fmt"
func partition(n, k int) int {
if n == 0 || k == 0 || (n < k) {
//  Outside the range
return 0
}
if k == 1 || k == n {
//  When single result possible
return 1
}
//  Count partition recursively
return (partition((n - 1), (k - 1)) + (k * partition((n - 1), k)))
}
//  Handles the request to count number of partition in subsets
func countPartition(n, k int) {
//  Display given data
fmt.Printf("\n Given n : %d", n)
fmt.Printf("\n Given k : %d", k)
//  Display calculated result
fmt.Printf("\n Total partition  : %d", partition(n, k))
}
func main() {
//  Test cases
countPartition(6, 3)
countPartition(5, 2)
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition  : 90
Given n : 5
Given k : 2
Total partition  : 15``````
``````/*
Java Program for
Treap implementation
*/
public class SubsetsPartition
{
public int partition(int n, int k)
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return partition(n - 1, k - 1) + k * partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
public void countPartition(int n, int k)
{
// Display given data
System.out.print("\n Given n : " + n);
System.out.print("\n Given k : " + k);
// Display calculated result
System.out.print("\n Total partition : " + partition(n, k));
}
public static void main(String[] args)
{
// Test cases
}
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````// Include namespace system
using System;
/*
Csharp Program for
Treap implementation
*/
public class SubsetsPartition
{
public int partition(int n, int k)
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
public void countPartition(int n, int k)
{
// Display given data
Console.Write("\n Given n : " + n);
Console.Write("\n Given k : " + k);
// Display calculated result
Console.Write("\n Total partition : " + this.partition(n, k));
}
public static void Main(String[] args)
{
// Test cases
}
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````<?php
/*
Php Program for
Treap implementation
*/
class SubsetsPartition
{
public	function partition(\$n, \$k)
{
if (\$n == 0 || \$k == 0 || \$k > \$n)
{
// Outside the range
return 0;
}
if (\$k == 1 || \$k == \$n)
{
// When single result possible
return 1;
}
// Count partition recursively
return \$this->partition(\$n - 1, \$k - 1) + \$k * \$this->partition(\$n - 1, \$k);
}
// Handles the request to count number of partition in subsets
public	function countPartition(\$n, \$k)
{
// Display given data
echo("\n Given n : ".\$n);
echo("\n Given k : ".\$k);
// Display calculated result
echo("\n Total partition : ".\$this->partition(\$n, \$k));
}
}

function main()
{
// Test cases
}
main();``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````/*
Node JS Program for
Treap implementation
*/
class SubsetsPartition
{
partition(n, k)
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
countPartition(n, k)
{
// Display given data
process.stdout.write("\n Given n : " + n);
process.stdout.write("\n Given k : " + k);
// Display calculated result
process.stdout.write("\n Total partition : " + this.partition(n, k));
}
}

function main()
{
// Test cases
}
main();``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````#    Python 3 Program for
#    Treap implementation
class SubsetsPartition :
def partition(self, n, k) :
if (n == 0 or k == 0 or k > n) :
#  Outside the range
return 0

if (k == 1 or k == n) :
#  When single result possible
return 1

#  Count partition recursively
return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k)

#  Handles the request to count number of partition in subsets
def countPartition(self, n, k) :
#  Display given data
print("\n Given n : ", n, end = "")
print("\n Given k : ", k, end = "")
#  Display calculated result
print("\n Total partition : ", self.partition(n, k), end = "")

def main() :
#  Test cases

if __name__ == "__main__": main()``````

#### input

`````` Given n :  6
Given k :  3
Total partition :  90
Given n :  5
Given k :  2
Total partition :  15``````
``````#    Ruby Program for
#    Treap implementation
class SubsetsPartition
def partition(n, k)
if (n == 0 || k == 0 || k > n)
#  Outside the range
return 0
end

if (k == 1 || k == n)
#  When single result possible
return 1
end

#  Count partition recursively
return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k)
end

#  Handles the request to count number of partition in subsets
def countPartition(n, k)
#  Display given data
print("\n Given n : ", n)
print("\n Given k : ", k)
#  Display calculated result
print("\n Total partition : ", self.partition(n, k))
end

end

def main()
#  Test cases
end

main()``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````/*
Scala Program for
Treap implementation
*/
class SubsetsPartition()
{
def partition(n: Int, k: Int): Int = {
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return partition(n - 1, k - 1) + k * partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
def countPartition(n: Int, k: Int): Unit = {
// Display given data
print("\n Given n : " + n);
print("\n Given k : " + k);
// Display calculated result
print("\n Total partition : " + partition(n, k));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubsetsPartition = new SubsetsPartition();
// Test cases
}
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````/*
Swift 4 Program for
Treap implementation
*/
class SubsetsPartition
{
func partition(_ n: Int, _ k: Int) -> Int
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
func countPartition(_ n: Int, _ k: Int)
{
// Display given data
print("\n Given n : ", n, terminator: "");
print("\n Given k : ", k, terminator: "");
// Display calculated result
print("\n Total partition : ", self.partition(n, k), terminator: "");
}
}
func main()
{
// Test cases
}
main();``````

#### input

`````` Given n :  6
Given k :  3
Total partition :  90
Given n :  5
Given k :  2
Total partition :  15``````
``````/*
Kotlin Program for
Treap implementation
*/
class SubsetsPartition
{
fun partition(n: Int, k: Int): Int
{
if (n == 0 || k == 0 || k > n)
{
// Outside the range
return 0;
}
if (k == 1 || k == n)
{
// When single result possible
return 1;
}
// Count partition recursively
return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
fun countPartition(n: Int, k: Int): Unit
{
// Display given data
print("\n Given n : " + n);
print("\n Given k : " + k);
// Display calculated result
print("\n Total partition : " + this.partition(n, k));
}
}
fun main(args: Array < String > ): Unit
{
// Test cases
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````
``````// Rust program
// Number of ways to partition a set into k subsets
fn main()  {
// Test cases
count_partition(6, 3);
count_partition(5, 2);
}
fn count_partition(n: i32, k: i32) {
// Display given data
print!("\n Given n : {}", n);
print!("\n Given k : {}", k);
// Display calculated result
print!("\n Total partition : {}", partition(n, k));
}
fn partition(n: i32, k: i32) -> i32 {
if n == 0 || k == 0 || k > n {
// Outside the range
return 0;
}
if k == 1 || k == n {
// When single result possible
return 1;
}
// Count partition recursively
return partition(n - 1, k - 1) + k * partition(n - 1, k);
}``````

#### input

`````` Given n : 6
Given k : 3
Total partition : 90
Given n : 5
Given k : 2
Total partition : 15``````

## Output Explanation

The code implements the algorithm and finds the number of ways to partition a set into k subsets based on the provided input. It demonstrates two test cases and displays the resulting number of ways.

## Time Complexity

The time complexity of this algorithm is O(n * k), where n is the number of elements in the set and k is the number of subsets. The dynamic programming approach with memoization ensures that overlapping subproblems are computed only once, resulting in an efficient solution.

## 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.