# C# – SoftUni – Natural Order Sequences

Another SoftUni algorithm problem that I have considered interesting is presented here:

You are given an integer S. Generate all non-empty sequences of numbers in range [1…S], which have sum of elements ≤ S. Display the sequences in their natural order, e.g. {1} ≤ {1, 1} ≤ … ≤ {2} ≤ {2, 1} ≤ {2, 1, 1} ≤ {2, 2}.

### Input

On the single input line you are given the number S.

### Output

• Print each sequence on separate line. The elements in a sequence must be separated by a single space.
• The elements in the sequences are distinct and their order matters: the sequences {1, 2} and {2, 1} are different and should both be printed.
• The sequences should be printed in their natural order (see the examples below).

### Constraints

• The number S is integer in the range [1 … 16].
• Time limit: 100 ms. Allowed memory: 24 MB.

What is the idea here? It is obvious, that it is some type of a recursion. If it was only with the 1, we may notice that they grow bigger and bigger. E.g., 1, 1 1, 1 1 1, etc. Thus, the loop is obvious and easy to implement. But we do not have only 1, we have other numbers as well. Thus, for 7 we should have “3 1 2 1” written somewhere. The question is where? 🙂 The answer is exactly below “3 1 2”

Long story short, try to debug the solution until you get it. Here comes the code:

Cheers! 🙂

Tagged with: , , ,