Taco Subset Sum Combinations

Given a positive integer \( N \), output all possible combinations of positive integers such that the sum of the numbers is \( N \). Each combination must be in non-decreasing order, and the overall list should be in lexicographical order.

In other words, find all sequences \( (a_1, a_2, \ldots, a_k) \) such that:

\[ \begin{cases} a_1 \leq a_2 \leq \cdots \leq a_k,\\ a_1 + a_2 + \cdots + a_k = N, \end{cases} \]

where each \( a_i \) is a positive integer.

inputFormat

A single line containing a positive integer ( N ).

outputFormat

Print each valid combination on its own line. In each line, print the numbers in the combination separated by a space.## sample

4

1 1 1 1
1 1 2
1 3
2 2
4

</p>