Find all possible sumation numbers to a specified sum

Question

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<List<int>> subsets = GetSubsets(sum);
 for (int i = 0; i < subsets.Count; i++)
 {
 Console.WriteLine(string.Join(",", subsets[i]));
 }
 Console.ReadKey();
 }
 private static List<List<int>> GetSubsets(int sum)
 {
 List<List<int>> subsets = new List<List<int>>();
 int[] allNumbers = new int[sum - 1];
 List<int> baseSubset = PopulateWith(1, allNumbers.Length + 1);
 int baseNumberIndex = 0;
 int additiveNumberIndex = 1;
 for (int i = 0; i < allNumbers.Length; i++)
 {
 allNumbers[i] = i + 1;
 }
 if (sum > 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 < allNumbers.Length && additiveNumberIndex < allNumbers.Length)
 {
 List<int> 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 (additiveNumberIndex == allNumbers.Length)
 {
 baseNumberIndex++;
 additiveNumberIndex = baseNumberIndex + 1;
 }
 }
 return subsets;
 }
 private static List<int> PopulateWith(int number, int size)
 {
 List<int> collection = new List<int>();
 for (int i = 0; i < size; i++)
 {
 collection.Add(number);
 }
 return collection;
 }

• I'll add comments tomorrow: "we have 3 as input the output will be (1, 1, 1),(1, 1, 2)" the second output is 4, did you mean (1, 2)?
• Denis: @I'lladdcommentstomorrow Yes my bad ..
• Ben Aaronson: For 3, would you also expect (2,1) and (3) as outputs?
• paparazzo: But sum(3) is 3 - it should count. Do you really need an int[] allNumbers? It will just be additiveNumberIndex + 1.
• Denis: @Paparazzi You're right there is no point of having allNumbers, but I still don't agree that 3 is a sum.

Answer 1

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<T> Singleton<T>(T t)
 {
 yield return t;
 }
 static IEnumerable<IEnumerable<int>> 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/

• Denis: I really like the design and shortness of code here but it works slower than mine.
• Eric Lippert: @denis: First, who cares? Do you have a user-focussed performance metric? Second, supposing we wished to performance optimize an algorithm; is it easier to optimize a four line algorithm or a 40 line algorithm? Third, your solution is not amenable to memoization optimizations. Look at the bigger picture here. You should be making the code right, and then elegant, and then fast. If you don't do it in that order you end up adding bugs when you try to optimize.
• Denis: I see thank you a lot for the comment & the answer.

Answer 2

Recursively breaks the number down into pairs.

//test
foreach (List<int> li in BreakMeDown(7).Distinct())
 Debug.WriteLine(string.Join(", ", li));
//end test

This is getting close. It produces all the answers but it produces duplicates.

 public static IEnumerable<List<int>> BreakMeDown5(int n)
 {
 for (int i = 1, j = n - 1; i <= j; i++, j--)
 {
 List<int> breakMeDown = new List<int>();
 breakMeDown.Add(i);
 breakMeDown.Add(j);
 yield return breakMeDown;
 foreach (List<int> li in BreakMeDown5(i))
 yield return breakMeDown.Skip(1)
 .Concat(li)
 .ToList();
 if (i != j)
 {
 foreach (List<int> li in BreakMeDown5(j))
 yield return breakMeDown.Take(1)
 .Concat(li)
 .ToList();
 }
 }
 }

• paparazzo: DVs it produces the answer and is super fast.
• t3chb0t: it produces the answer and is super fast this doesn't matter. This is Code Review and not suggest-an-alternative-version. You post a lot of solutions but without reviewing the code. This is not the purpose of this site. You don't even write why your code is faster. You never explain what you did.
• paparazzo: @t3chb0t See accepted answer. Question "I don't think that the code is really efficient so any tips are appreciated."
• t3chb0t: This is Eric, he gets 5k upvotes for just posting an answer, it's a completely different category.
• t3chb0t: any tips are appreciated - where is your answer giving any tips?