This paper proposes a new algorithm to generate a minimal search space of the problem of coalition structure generation using a new optimal integer partition. The new partition includes only partitions giving optimal coalition structures. These partitions are those containing 1 at most one element. Our new algorithm generates optimal partition structures in two steps. The first step, we use a modified version of ZSl algorithm to generate the optimal integer partition of input integer. We then use the partition to generate optimal coalition structures in the second step.