Find all possible sumation numbers to a specified sum

This is a problem that I had in mind for a loong time and today I decided to give it a go, the basic idea is you enter a number/sum and the program outputs all the possible ways this sum can be formed let's say we have 3 as input the output will be (1, 1, 1),(1, 2) I don't think that the code is really efficient so any tips are appreciated.

```
static void Main(string[] args)
{
int sum = int.Parse(Console.ReadLine());
List> subsets = GetSubsets(sum);
for (int i = 0; i > GetSubsets(int sum)
{
List> subsets = new List>();
int[] allNumbers = new int[sum - 1];
List baseSubset = PopulateWith(1, allNumbers.Length + 1);
int baseNumberIndex = 0;
int additiveNumberIndex = 1;
for (int i = 0; i 1)
{
// if 1 is entered as a sum we dont want to return 1 as result because that's not a sum of numbers it's just 1.
subsets.Add(baseSubset);
}
while (baseNumberIndex currentSubset = PopulateWith(allNumbers[baseNumberIndex], (int)Math.Round((double)sum / allNumbers[baseNumberIndex]));
int currentSum = currentSubset.Sum();
while (true)
{
if (currentSum + allNumbers[additiveNumberIndex] > sum)
{
currentSubset.Remove(allNumbers[baseNumberIndex]);
}
else
{
currentSubset.Add(allNumbers[additiveNumberIndex]);
}
currentSum = currentSubset.Sum();
if (currentSum == sum && !subsets.Any(seq => seq.SequenceEqual(currentSubset)))
{
subsets.Add(currentSubset.ToList());
}
if (currentSum + allNumbers[additiveNumberIndex] > sum && !currentSubset.Contains(allNumbers[baseNumberIndex]))
{
break;
}
}
additiveNumberIndex++;
if

Rather than go through a line-by-line critique of your program, let me just say:

• It is way too long and too complicated

• You are getting hung up on all the adds and removes. This problem is much easier to solve if you never add or remove anything. Treat sequences as immutable data structures.

You should be able to do this in about four lines of code in your method body, and some little helper methods. Here's an example:

using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
    static IEnumerable Singleton(T t)
    {
        yield return t;
    }
    static IEnumerable> AllSums(int n, int min = 1)
    {
        for (int i = min; i <= n / 2; ++i)
            foreach(var seq in AllSums(n - i, i))
                yield return Singleton(i).Concat(seq);
        yield return Singleton(n);
    }
    public static void Main()
    {
        foreach(var result in AllSums(7))
            Console.WriteLine(string.Join(",", result));
    }
}

The key here is to make a clear specification for the AllSums method. It takes positive integers n and min and returns a sequence of sequences that all have the following properties:

• They sum to n

• The smallest number in the sequence is not smaller than min

• The sequence is non-decreasing

Once you have a method that has these properties, the recursion becomes much easier to reason about.

Go through this implementation very carefully and annotate each line of code with its meaning and purpose in the algorithm.

For another application of this general principle of generating a sequence of data structures that all have a sum property, see my series of articles which begins here:

https://blogs.msdn.microsoft.com/ericlippert/2010/04/19/every-binary-tree-there-is/

StackExchange Code Review Q#144501, answer score: 6