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&lt;List&lt;int&gt;&gt; subsets = GetSubsets(sum);
        for (int i = 0; i &lt; subsets.Count; i++)
        {
            Console.WriteLine(string.Join(",", subsets[i]));
        }
        Console.ReadKey();
    }

    private static List&lt;List&lt;int&gt;&gt; GetSubsets(int sum)
    {
        List&lt;List&lt;int&gt;&gt; subsets = new List&lt;List&lt;int&gt;&gt;();
        int[] allNumbers = new int[sum - 1];
        List&lt;int&gt; baseSubset = PopulateWith(1, allNumbers.Length + 1);
        int baseNumberIndex = 0;
        int additiveNumberIndex = 1;
        for (int i = 0; i &lt; allNumbers.Length; i++)
        {
            allNumbers[i] = i + 1;
        }
        if (sum &gt; 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 &lt; allNumbers.Length &amp;&amp; additiveNumberIndex &lt; allNumbers.Length)
        {
            List&lt;int&gt; currentSubset = PopulateWith(allNumbers[baseNumberIndex], (int)Math.Round((double)sum / allNumbers[baseNumberIndex]));
            int currentSum = currentSubset.Sum();
            while (true)
            {
                if (currentSum + allNumbers[additiveNumberIndex] &gt; sum)
                {
                    currentSubset.Remove(allNumbers[baseNumberIndex]);
                }
                else
                {
                    currentSubset.Add(allNumbers[additiveNumberIndex]);
                }
                currentSum = currentSubset.Sum();
                if (currentSum == sum &amp;&amp; !subsets.Any(seq =&gt; seq.SequenceEqual(currentSubset)))
                {
                    subsets.Add(currentSubset.ToList());
                }
                if (currentSum + allNumbers[additiveNumberIndex] &gt; sum &amp;&amp; !currentSubset.Contains(allNumbers[baseNumberIndex]))
                {
                    break;
                }
            }
            additiveNumberIndex++;
            if (additiveNumberIndex == allNumbers.Length)
            {
                baseNumberIndex++;
                additiveNumberIndex = baseNumberIndex + 1;
            }
        }
        return subsets;
    }

    private static List&lt;int&gt; PopulateWith(int number, int size)
    {
        List&lt;int&gt; collection = new List&lt;int&gt;();
        for (int i = 0; i &lt; size; i++)
        {
            collection.Add(number);
        }
        return collection;
    }
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&lt;T&gt; Singleton&lt;T&gt;(T t)
    {
        yield return t;
    }
    static IEnumerable&lt;IEnumerable&lt;int&gt;&gt; AllSums(int n, int min = 1)
    {
        for (int i = min; i &lt;= 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/