An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums

We present a polynomial time algorithm, which solves a nonstandard Variation of the well-known PARTITION-problem: Given positive integers $n,k$ and $t$ such that $t\ge n$ and $k\cdot t=\left(\genfrac{}{}{0px}{}{n+1}{2}\right)$, the algorithm partitions the elements of the set $I_n=\{1,\dots ,n\}$ into $k$ mutually disjoint subsets $T_j$ such that ${\cup }_{j=1}^k{T}_j=I_n$ and $\sum_{x \in T_{j}} x = t$foreach$j \in {1,2, \ldots, k}$\mathrm{.}Thealgorithmneeds$$\mathcal{O}$(n \cdot ( \frac{n}{2k} + \log \frac{n(n+1)}{2k} ))$ steps to insert the $n$ elements of $I_n$ into the $k$ sets $T_j$.