In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that number of elements in the original set always equals to the sum of number of elements in each partition.

Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:

• The family P does not contain the empty set
• The union of the sets in P is equal to X. The sets in P are said to cover X.
• The intersection of any two distinct sets in P is empty i.e. the elements of P are said to be pairwise disjoint.

The number of possible partition of a set of n elements is B(n) known as Bell number. As we know, this problem is NP-Complete i.e. it has non-polynomial time solution.

Also read: Multiset Partitioning Problem – Only Code

Solving for a smaller set in Polynomial time

But for a smaller set we could try to find a way to generate all partitions.
Let’s take an example, given a collection of numbers that may contain duplicates, find all partitions of it. (all possible ways of dividing the collection.)
For a set i.e. when each element in multiset has multiplicity 1, there’s a nice solution here. But it doesn’t solve the problem when there are duplicate elements present in the set.

For instance, the multiset {1, 1, 2} has 4 partitions:
partition 1 = { {1}, {1}, {2} }
partition 2 = { {1}, {1, 2} }
partition 3 = { {1, 1}, {2} }
partition 4 = { {1, 1, 2} }

It can be solved using backtracking and recursion. This C++ program might be useful.

//Working Code in C++

void solve (set<vector<vector<int>>>& solution, vector<int> inputSet,  
vector<vector<int>>& partitions, vector<int> partition, int n, int i) { 
    int numberOfElements = 0; 
    for (int i=0; i<partitions.size(); i++) { 
        numberOfElements += partitions[i].size(); 
    } 
    if (numberOfElements == n) { 
        vector<vector<int>> newPartitions = partitions; 
        for (int i=0; i<newPartitions.size(); i++) { 
            sort (newPartitions[i].begin(), newPartitions[i].end()); 
        } 
        sort(newPartitions.begin(), newPartitions.end()); 
        solution.insert(newPartitions); 
        return;   
    } 
    for (int j=i; j<n; j++) { 
        partition.push_back(inputSet[j]); 
        partitions.push_back(partition); 
        vector<int> partitionNew; 
        solve(solution, inputSet, partitions, partitionNew, n, j+1); 
        partitions.pop_back(); 
    } 
} 
 
void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) { 
    if (i == n) { 
        vector<int> partition; 
        vector<vector<int>> partitions; 
        solve(solution, inputSet, partitions, partition, inputSet.size(), 0); 
        return; 
    } 
    for (int j=i; j<=n; j++) { 
        swap(inputSet[i], inputSet[j]); 
        permute(solution, inputSet, i+1, n); 
        swap(inputSet[i], inputSet[j]); 
    } 
} 

Here’s the working example: Generate all Partitions

Thanks