Integer Partitions in Non-Increasing Order

Given a non-negative integer \(n\), your task is to generate and display all of its partitions in non-increasing order. An integer partition of \(n\) is a way of writing \(n\) as a sum of positive integers where the order of the summands does not matter. In this problem, each partition must be printed on a separate line, with the individual numbers separated by a plus sign (+).

For example, if \(n = 4\), the partitions are:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

The algorithm should generate the partitions recursively ensuring that the parts are in non-increasing order. Note that when \(n = 0\), the program should output a blank line (i.e. an empty partition).

inputFormat

The input consists of a single line containing one non-negative integer \(n\) (\(0 \leq n\)).

outputFormat

Output all partitions of the number \(n\) in non-increasing order, one partition per line. In each partition, the summands should be separated by the string + .

## sample

4

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

</p>