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

Question

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

例如，如果输入为 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

这是一个不使用集合（仅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是允许的最大总和。