algorithm - 如何找到所有方法来获得一个整数 n 作为 m 个整数的总和(无序)？

Question

我正在寻找一种算法，它可以找到将整数 n 表示为 m(非负)整数之和的所有方法。我对 m=6 和 n20 特别感兴趣。找到所有可能性的最快方法是什么(使用计算机，而不是手工)。如果可能的话，我只想看六个整数的组合，顺序不相关(即 [1, 2, 0, 0, 0, 0] 和 [2, 1, 0, 0, 0, 0 ] 算作 1 个组合)。

最简单的方法是简单地尝试所有具有小于或等于 20 的 6 个整数的排列，并且只将总和为 20 的那些添加到我们的结果中(如果我们不想查看顺序，则删除 double ) .然而，这似乎会花费很长时间，因为 20^6 种可能性将需要相当长的时间来检查。

解决这个问题的更有效方法是什么？

Answer 1

您可以通过按单调递增顺序生成数字(每个数字等于或大于前一个数字)来避免重复。

对于给定的 count(例如 6)，您可以递归地定义问题，方法是为第一个数字生成所有可能的值，然后递归地生成 count - 1< 的所有列表 总和等于原始总和减去第一个数字的数字，第一个数字是列表中剩余数字的最小值。

因为数字需要增加，所以您不能“过早达到峰值”- 您可以通过总和除以计数来计算最大值(因为所有剩余值都必须等于或大于此值) .

这是一个简单的 Java 实现:

public static void outputSums(String start, int sum, int count, int min)
{
    // if there is just one value, it's just the sum:
    if(count == 1)
    {
        System.out.println(start + " " + sum);
        return;
    }

    int max = sum / count;  // calculate maximum value
    for(int i = min; i <= max; i++)
    {
        outputSums(start + " " + i,  // append each number to the list
            sum - i,  // recursively find numbers that sum to the remainder
            count - 1,   // with a count of one less
            i);   // equal to or greater to this one (i.e. increasing order)
    }
}

start 包含您目前输出的部分列表。当您第一次调用该函数时，它将为空。

Demo