Given a set A = {1, 2, 3, . . ., n }. It is called a partition of the set A if the following conditions follow:
- The union of all the sets is the set A
- The intersection of any two sets is an empty set
Examples:
Input: n = 3
Output: [{1, 2, 3}], [{1, 2}, {3}], [{1, 3}, {2}], [{1}, {2, 3}], [{1}, {2}, {3}]
Explanation: For the set {1, 2, 3} these are 5 possible partitions [{1, 2, 3}], [{1, 2}, {3}], [{1, 3}, {2}], [{1}, {2, 3}], [{1}, {2}, {3}]Input: n = 1
Output: {1}
Explanation: For the set {1} these is 1 possible partitions {1}
Approach: To solve the problem follow the below idea:
The idea is to use recursion to generate all possible partition of a given set, for each element in the set we will either add it to existing subsets or create a singleton subset and we will repeat this process for all elements in the sets until we have considered all the elements and will print each partition.
Below are the steps for the above approach:
- Initialize an empty list ans to store all the partitions.
- Create a recursive function Partition that takes the set, an index, and the list ans as parameters.
- If the index is equal to the size of the set, then print the partition and return it.
- Now check if we have considered all the elements in the sets, then push the partition into ans and return.
- Now add the current element to each subset in the partition and recall the new partition and index values then remove the current subset element.
- Add the current element as a singleton subset and recall the Partition function with the updated partition and index values.
- Call the allpartition function with the set as input to generate all partitions for a given set.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to print a partitionvoid printPartition(vector<vector<int> > ans){ for (auto i : ans) { cout << "{ "; for (auto element : i) { cout << element << " "; } cout << "} "; } cout << endl;}// Function to generate all partitionsvoid Partition(vector<int> set, int index, vector<vector<int> >& ans){ // If we have considered all elements // in the set print the partition if (index == set.size()) { printPartition(ans); return; } // For each subset in the partition // add the current element to it // and recall for (int i = 0; i < ans.size(); i++) { ans[i].push_back(set[index]); Partition(set, index + 1, ans); ans[i].pop_back(); } // Add the current element as a // singleton subset and recall ans.push_back({ set[index] }); Partition(set, index + 1, ans); ans.pop_back();}// Function to generate all// partitions for a given setvoid allPartitions(vector<int> set){ vector<vector<int> > v; Partition(set, 0, v);}// Main functionint main(){ // The size of the set int n = 3; // Initialize the set as // {1, 2, ..., n} vector<int> set(n); for (int i = 0; i < n; i++) { set[i] = i + 1; } cout << "All partition of the set will be : " << endl; // Generate all partitions of the set allPartitions(set); return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class PartitionGenerator { // Function to print a partition static void printPartition(List<List<Integer>> ans) { for (List<Integer> subset : ans) { System.out.print("{ "); for (int element : subset) { System.out.print(element + " "); } System.out.print("} "); } System.out.println(); } // Function to generate all partitions static void partition(List<Integer> set, int index, List<List<Integer>> ans) { // If we have considered all elements // in the set, print the partition if (index == set.size()) { printPartition(ans); return; } // For each subset in the partition, // add the current element to it and recall for (int i = 0; i < ans.size(); i++) { ans.get(i).add(set.get(index)); partition(set, index + 1, ans); ans.get(i).remove(ans.get(i).size() - 1); } // Add the current element as a singleton subset and recall List<Integer> newSubset = new ArrayList<>(); newSubset.add(set.get(index)); ans.add(newSubset); partition(set, index + 1, ans); ans.remove(ans.size() - 1); } // Function to generate all partitions for a given set static void allPartitions(List<Integer> set) { List<List<Integer>> partitions = new ArrayList<>(); partition(set, 0, partitions); } // Main function public static void main(String[] args) { // The size of the set int n = 3; // Initialize the set as {1, 2, ..., n} List<Integer> set = new ArrayList<>(); for (int i = 0; i < n; i++) { set.add(i + 1); } System.out.println("All partitions of the set will be: "); // Generate all partitions of the set allPartitions(set); }}// This code was contirbuted by codearcade |
Python3
def print_partition(ans): """ Function to print a partition """ for i in ans: print("{", end=" ") for element in i: print(element, end=" ") print("}", end=" ") print()def partition_set(set, index, ans): """ Function to generate all partitions """ if index == len(set): # If we have considered all elements in the set, print the partition print_partition(ans) return # For each subset in the partition, add the current element to it and recall for i in range(len(ans)): ans[i].append(set[index]) partition_set(set, index + 1, ans) ans[i].pop() # Add the current element as a singleton subset and recall ans.append([set[index]]) partition_set(set, index + 1, ans) ans.pop()def all_partitions(set): """ Function to generate all partitions for a given set """ ans = [] partition_set(set, 0, ans)# Main functionif __name__ == "__main__": # The size of the set n = 3 # Initialize the set as {1, 2, ..., n} set = list(range(1, n + 1)) print("All partitions of the set will be:") # Generate all partitions of the set all_partitions(set) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to print a partition static void PrintPartition(List<List<int>> ans) { foreach (var i in ans) { Console.Write("{ "); foreach (var element in i) { Console.Write(element + " "); } Console.Write("} "); } Console.WriteLine(); } // Function to generate all partitions static void Partition(List<int> set, int index, List<List<int>> ans) { // If we have considered all elements // in the set print the partition if (index == set.Count) { PrintPartition(ans); return; } // For each subset in the partition // add the current element to it // and recall for (int i = 0; i < ans.Count; i++) { ans[i].Add(set[index]); Partition(set, index + 1, ans); ans[i].RemoveAt(ans[i].Count - 1); } // Add the current element as a // singleton subset and recall ans.Add(new List<int> { set[index] }); Partition(set, index + 1, ans); ans.RemoveAt(ans.Count - 1); } // Function to generate all // partitions for a given set static void AllPartitions(List<int> set) { List<List<int>> v = new List<List<int>>(); Partition(set, 0, v); } static void Main(string[] args) { // The size of the set int n = 3; // Initialize the set as // {1, 2, ..., n} List<int> set = new List<int>(n); for (int i = 0; i < n; i++) { set.Add(i + 1); } // Generate all partitions of the set Console.WriteLine("All partitions of the set will be:"); AllPartitions(set); }} |
Javascript
// Function to print a partitionfunction printPartition(ans) { for (let i of ans) { process.stdout.write("{ "); for (let element of i) { process.stdout.write(element + " "); } process.stdout.write("} "); } process.stdout.write("\n");}// Function to generate all partitionsfunction Partition(set, index, ans) { // If we have considered all elements // in the set print the partition if (index === set.length) { printPartition(ans); return; } // For each subset in the partition // add the current element to it // and recall for (let i = 0; i < ans.length; i++) { ans[i].push(set[index]); Partition(set, index + 1, ans); ans[i].pop(); } // Add the current element as a // singleton subset and recall ans.push([set[index]]); Partition(set, index + 1, ans); ans.pop();}// Function to generate all// partitions for a given setfunction allPartitions(set) { let ans = []; Partition(set, 0, ans);}// Main functionfunction main() { // The size of the set let n = 3; // Initialize the set as // {1, 2, ..., n} let set = Array.from({ length: n }, (_, i) => i + 1); process.stdout.write("All partitions of the set will be:\n"); // Generate all partitions of the set allPartitions(set);}// Invoke the main functionmain(); |
Output
All partition of the set will be :
{ 1 2 3 }
{ 1 2 } { 3 }
{ 1 3 } { 2 }
{ 1 } { 2 3 }
{ 1 } { 2 } { 3 }
Time Complexity: O(2n), where n is the number of elements
Auxiliary Space: O(2n), where n is the number of elements as we are creating a vector of vectors to store all possible partitions
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
