Sum combinations that add up to a given natural number

Here is a solution not using collections (only using System;) and generating the output in the required order.

public static void PrintCombinations(int n)
{
    PrintRest("", 0, n, n - 1);
}

private static void PrintRest(string listStart, int startSum, int n, int max)
{
    for (int i = 1; i <= max; i++) {
        string list = listStart.Length > 0
            ? listStart + " + " + i.ToString()
            : i.ToString();
        int sum = startSum + i;
        if (sum == n) {
            Console.WriteLine(list);
        } else if (sum < n) {
            PrintRest(list, sum, n, i);
        }
    }
}

You would call it as

PrintCombinations(7);

It starts by taking all possible start summands and calling itself to construct the rest of the sum. The combinations up to the current point are passed as string parameter listStart. The sum it represents is passed as int startSum. The target sum is n. max is the biggest summand allowed.

Try following :

    class Program
    {
        static List<string> combinationList = new List<string>();
        const int SUM = 7;
        static void Main(string[] args)
        {
            List<int> numbers = new List<int>();
            GenerateCombinations(numbers, 0);
            combinationList.Sort();
            Console.WriteLine(string.Join("\n", combinationList));

            Console.ReadLine();
          
        }
        static void GenerateCombinations(List<int> numbers, int sum)
        {
            int start = 1;
            if (numbers.Count > 0) start = numbers[0]; 
                
            for (int i = start; i <= SUM; i++)
            {
                int newSum = sum + i;
                
                if (newSum > SUM) break;
                
                List<int> newList = new List<int>(numbers);
                newList.Insert(0,i);

                if (newSum == SUM)
                {
                    combinationList.Add(string.Join(" + ", newList));
                    break;
                }
                else
                {
                    GenerateCombinations(newList, newSum);
                }

            }
        }
    }

Since you are looking for a recursive solution, let's do it recursively without Linq and other mean.

Let's start from the basic: when given 0, we have an empty solution:

    private static int[][] Solutions(int value) {
      if (value <= 0)
        return new int[][] { new int[0] };

      //TODO: other cases for 1, 2, ... 
    }

Time to do the next step: if we know how to solve for some n - 1 (n - 1 >= 0) we can solve for n as follow: all solutions start from m (m < n) are in form

`m + solutions for n - m which uses m .. 1 only`

E.g.

6 + 1                      <- starts from 6, solves for 7 - 6 = 1, uses 6..1 only 
5 + 2                      ...
5 + 1 + 1
4 + 3
4 + 2 + 1
4 + 1 + 1 + 1              ... 
3 + 3 + 1                  <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3 + 2 + 2                  <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only 
3 + 2 + 1 + 1              <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3 + 1 + 1 + 1 + 1          ...
2 + 2 + 2 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1      ... 
1 + 1 + 1 + 1 + 1 + 1 + 1  <- starts from 1, solves for 7 - 1 = 6, uses 1..1 only

This recursion can be encoded as

    private static int[][] Solutions(int value, int startWith = -1) {
      if (value <= 0)
        return new int[][] { new int[0] };

      if (startWith < 0)
        startWith = value - 1;

      List<int[]> solutions = new List<int[]>();

      for (int i = Math.Min(value, startWith); i >= 1; --i) 
        foreach (int[] solution in Solutions(value - i, i)) {
          int[] next = new int[solution.Length + 1];

          Array.Copy(solution, 0, next, 1, solution.Length);
          next[0] = i;

          solutions.Add(next);
        }
      
      // Or just (if we are allow a bit of Linq)
      //   return solutions.ToArray();
      int[][] answer = new int[solutions.Count][];

      for (int i = 0; i < solutions.Count; ++i)
        answer[i] = solutions[i];

      return answer;
    }

Demo

var result = Solutions(7);

// A pinch of Linq for demonstration
string report = string.Join(Environment.NewLine, result
  .Select(solution => string.Join(" + ", solution)));

Console.Write(report);

Outcome:

6 + 1
5 + 2
5 + 1 + 1
4 + 3
4 + 2 + 1
4 + 1 + 1 + 1
3 + 3 + 1
3 + 2 + 2
3 + 2 + 1 + 1
3 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1