A Smart Backtracking Algorithm for Computing Set Partitions with Parts of Certain Sizes

Let $α=\{a_1,a_2,a_3,...,a_n\}$ be a set of elements, $δ< n$ be a non-negative integer, and $Γ: α\to \{0, 1, 2, ..., n\}$ be a total mapping. Then, we call $Γ$ a \emph{partition} of $α$ if and only if for all $x \in α$, $Γ(x) \neq 0$. Further, we call $Γ$ a $δ$-\emph{partition} of $α$ if and only if $Γ$ is a partition of $α$ and for all $i \in \{1, 2, 3, ..., n\}$, $|\{x: Γ(x)=i\}| > δ$. We give a non-trivial algorithm that computes all $δ$-partitions of $α$ in $Ω(n)$ time. On the opposite, a naive generate-and-test algorithm would compute all $δ$-partitions of $α$ in $Ω(nB_n)$ time where $B_n$ is the Bell number.