Partitions into distinct summands HARD Backtracking (BAC) 50 XP 0 solved
Mobile coding works. A laptop is faster for long sessions.

Problem

Read a positive natural number `n`. Generate and print, in lexicographic order, all decompositions of `n` as a sum of **strictly increasing** positive natural numbers (all terms are distinct, and on each line they are written in ascending order). On the last line print the total number of decompositions found.

Input format

Input input.txt

The program reads from standard input a single natural number, `n`. - `1 <= n <= 12` - A decomposition must have at least one term, so `n` itself is a valid decomposition (with a single term).

Output format

Output output.txt

The program prints, one per line, all decompositions of `n` as a sum of strictly increasing positive integers. The terms of each decomposition are separated by spaces with no trailing space. Decompositions are printed in lexicographic order (those starting with smaller values come first). On the last line print the total number of decompositions.

Example

input
6
output
1 2 3
1 5
2 4
6
4

Ready to solve this challenge?

Create a free account to write code, submit solutions, and track your progress.

⌨️ Keyboard Shortcuts

Code Editor
Run Code
Ctrl Enter
Submit Code
Ctrl Shift Enter
Format Code
Shift Alt F
Toggle Comment
Ctrl /
Undo
Ctrl Z
Redo
Ctrl Y
Navigation
Global Search
/
Show Shortcuts
?
Close Modal
Esc

🔍 Interactive Debugger

0 / 0

Analyzing your code...

📦 Variables

No variables yet

📚 Call Stack
main() line 1
📤 Output
We use cookies

Essential cookies are always active. You can choose to enable preference and analytics cookies. Learn more