Trying to generate all sequences of specified numbers up to a max sum

Question

Given the following list of descending unique numbers (3,2,1) I wish to generate all the sequences consisting of those numbers up to a maximum sum.

Let's say that the sum should be below 10. Then the sequences I'm after are:

3 3 3
3 3 2 1
3 3 2
3 3 1 1 1
3 3 1 1
3 3 1
3 3
3 2 2 2
3 2 2 1 1
3 2 2 1
3 2 2
3 2 1 1 1 1
3 2 1 1 1
3 2 1 1
3 2 1
3 2
3 1 1 1 1 1 1
3 1 1 1 1 1
3 1 1 1 1
3 1 1 1
3 1 1
3 1
3
2 2 2 2 1
2 2 2 2
2 2 2 1 1 1
2 2 2 1 1
2 2 2 1
2 2 2
2 2 1 1 1 1 1
2 2 1 1 1 1
2 2 1 1 1
2 2 1 1
2 2 1
2 2
2 1 1 1 1 1 1 1
2 1 1 1 1 1 1
2 1 1 1 1 1
2 1 1 1 1
2 1 1 1
2 1 1
2 1
2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1
1

I'm sure that there's a "standard" way to generate this.

I thought of using linq but can't figure it out. Also, I am trying a stack based approach but I am still not successful.

Any idea?

Answer 1

I think this is easiest to write recursively, something which pure LINQ isn't that great for. So it's probably best to implement this as an ordinary recursive function. Pass as a parameter the amount you have left from your maximum total and every time you add en element, call the function recursively, reducing the total appropriately:

IEnumerable<IEnumerable<int>> sequences(IEnumerable<int> set, int maxTotal)
{
    foreach (int i in set.Where(x => x <= maxTotal))
    {
        yield return new int[] { i };
        foreach (var s in sequences(set.Where(x => x <= i), maxTotal - i))
            yield return (new int[] { i }).Concat(s);
    }
}

void Run()
{
    foreach (var z in sequences(new int[] { 3, 2, 1 }, 10))
    {
        Console.WriteLine(
            string.Join(" ", z.Select(x => x.ToString()).ToArray())
        );
    }
}

Result:

3
3 3
3 3 3
3 3 3 1
3 3 2
3 3 2 2
3 3 2 1
3 3 2 1 1
3 3 1
3 3 1 1
3 3 1 1 1
...
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Note that this isn't the most efficient solution.