C# – SoftUni – Natural Order Sequences

Posted on October 4, 2017 by

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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Sequences
{
    static StringBuilder stringBuilder = new StringBuilder();
    static void Main()
    {
        int readSum = int.Parse(Console.ReadLine());
        List<int> variations = new List<int>(new int[readSum]);
        GenerateSequence(0, 0, readSum, variations);
        Console.WriteLine(stringBuilder);
    }

    public static void GenerateSequence(int idx, int currSum, int readSum, List<int> variations)
    {

        if (currSum <= readSum && currSum!=0)
        {
            stringBuilder.AppendLine(string.Join(" ", variations.TakeWhile(x => x != 0)));
        }

        if (currSum >= readSum || idx >= variations.Count)
        {
            return;
        }

        for (int i = 1; i <= readSum; i++)
        {
            variations[idx] = i;
            GenerateSequence(idx + 1, currSum + i, readSum, variations);
        }
        variations[idx] = 0;
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

class Sequences

{

static StringBuilder stringBuilder = new StringBuilder();

static void Main()

{

int readSum = int.Parse(Console.ReadLine());

List<int> variations = new List<int>(new int[readSum]);

GenerateSequence(0, 0, readSum, variations);

Console.WriteLine(stringBuilder);

}

public static void GenerateSequence(int idx, int currSum, int readSum, List<int> variations)

{

if (currSum <= readSum && currSum!=0)

{

stringBuilder.AppendLine(string.Join(" ", variations.TakeWhile(x => x != 0)));

}

if (currSum >= readSum || idx >= variations.Count)

{

return;

}

for (int i = 1; i <= readSum; i++)

{

variations[idx] = i;

GenerateSequence(idx + 1, currSum + i, readSum, variations);

}

variations[idx] = 0;

}

Cheers! 🙂

Tagged with: algorithm, C#, Natural order sequences, recursion

C# – SoftUni – Natural Order Sequences

Input

Output

Constraints

Related posts: