加起来等于给定自然数的组合

Question

过去一周我一直在努力解决这个非常棘手的问题 :( 我必须使用递归找到总和为给定自然数的所有数字组合。我不允许使用 LINQ 或任何东西else 除了“使用系统”

例如，如果输入为 7，则输出应如下所示：

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

组合中的数字应完全按照该顺序列出，例如输入 3，输出应完全如下所示：

1 + 1 + 1
2 + 1

对于 4 的输入，输出应如下所示：

1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 + 1

对于每个新的组合列表，我们都会递增列表中的第一个数字，然后我们继续前一个列表的剩余部分，直到总和等于输入。

1（包括 1）和输入 - 1 之间只允许正数。

到目前为止，我的代码为相同的给定输入 7 提供了以下输出：

+ 1
 + 1 + 1 + 2
 + 1 + 1 + 1
 + 2 + 2 + 3
 + 1 + 1 + 1
 + 1 + 1 + 2
 + 2 + 1
 + 1 + 1 + 2
 + 2 + 2 + 1
 + 3 + 3 + 4
 + 1 + 1 + 1
 + 1 + 1 + 2
 + 1 + 1 + 1
 + 2 + 2 + 3
 + 2 + 1
 + 1 + 1 + 2
 + 1 + 1 + 1
 + 2 + 2 + 3
...

你能帮我提点建议吗？

static string GenerateCombinations(int n)        
{
    string combinationList = "";

    for (int index = 1; index < n - 1; index++)
    {
        string intermediaryList = GenerateCombinations(n - index, index) + " + " + index;

        combinationList += intermediaryList;
    }

    return combinationList + "\n";
}

static string GenerateCombinations(int n, int index)
{
    string combinationList = "";

    for (int i = 1; i < n - 1; i++)
    {
        if (i <= index)
        {
            string intermediaryList = GenerateCombinations(n) + " + " + index;

            combinationList += intermediaryList;
        }
    }

    return combinationList;
}

static void Main()
{
    int n = Convert.ToInt32(Console.ReadLine());

    Console.WriteLine(GenerateCombinations(n));
}

Answer 1

尝试以下操作：

    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);
                }

            }
        }
    }

Answer 2

由于您正在寻找递归解决方案，所以让我们在没有 Linq 和其他均值的情况下递归地进行。

让我们从基础开始：当给定 0 时，我们有一个空解：

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

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

是时候进行下一步了：如果我们知道如何求解某些 n - 1 (n - 1 >= 0)，我们可以如下求解 n：所有从 m (m < n) 开始的解决方案都采用

形式

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

例如

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

这个递归可以编码为

    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;
    }

演示

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);

结果：

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

Answer 3

这是一个不使用集合（仅 using System;）并按要求的顺序生成输出的解决方案。

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);
        }
    }
}

你可以称它为

PrintCombinations(7);

它首先获取所有可能的开始加数并调用自己来构造其余的总和。到当前点的组合作为字符串参数 listStart 传递。它表示的总和作为 int startSum 传递。目标总和为 n。 max 是允许的最大加数。

加起来等于给定自然数的组合

Sum combinations that add up to a given natural number

c#

algorithm

recursion