0120. Number Partitions

Input file name:	part.in
Output file name:	part.out
Time limit:	500 ms
Memory limit:	64 megabytes

A partition of a number n is a set of integer positive numbers d₁ ≥ d₂ ≥ …≥ d_k such that Σ_i=1^k d_i = n

Generate all partitions of a given number in anti-lexicographical order.

Input file

Input number contains one integer positive number n, 1 ≤ n ≤ 30.

Output file

Output file should contain all partitions of a number n, one partition at a line, in anti-lexicographical order.

Examples:

part.in	part.out
3	3 2+1 1+1+1

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version