まず、出力直前にソートすればよいですから、辞書順という条件は無視してお好きな順序で生成して OK です。

そこで、逆辞書順 (列の reverse に関する辞書順) で生成しましょう。すると、途中でいかなる値になろうとも最後に \(1\) の個数で調整できるため、適当に全部再帰しても無駄がなく、間に合います。