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.

saving


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! 🙂

About

VBA Developer

Tagged with: , , ,