给定整数作为输入，打印所有唯一整数分区

一尘不染

给定整数作为输入，打印所有唯一整数分区

algorithm

我正在解决编程问题，遇到一个无法令人满意地找到解决方案的问题。问题如下：

Print all unique integer partitions given an integer as input.
Integer partition is a way of writing n as a sum of positive integers.

例如：输入= 4，则输出应为输出=

我应该如何考虑解决这个问题？我想知道使用递归。谁能为我提供这个问题的算法？或提示解决方案。欢迎对此类问题进行任何解释。（我是编程世界的初学者）谢谢！

阅读 254

2020-07-28

共1个答案

一尘不染

我会这样处理：

首先，概括问题。您可以定义一个功能

printPartitions(int target, int maxValue, string suffix)

规格：

打印目标的所有整数分区，后跟后缀，以使分区中的每个值最多为maxValue

请注意，始终至少有1个解决方案（假设target和maxValue均为正），全为1。

您可以递归使用此方法。因此，首先考虑一下基本情况：

printPartitions(0, maxValue, suffix)

应该简单地打印suffix。

如果target不是0，则必须选择：不使用maxValue（如果maxValue > target只有一个选项：不要使用）。如果你不使用它，你应该降低maxValue的1。

那是：

if (maxValue <= target)
    printPartitions(target-maxValue, maxValue, maxValue + suffix);
if (maxValue > 1)
    printPartitions(target, maxValue-1, suffix);

结合所有这些，就可以得到一个相对简单的方法（这里用Java编码，我对语句进行了一些重新排序，以获得与您描述的完全相同的顺序）：

void printPartitions(int target, int maxValue, String suffix) {
    if (target == 0)
        System.out.println(suffix);
    else {
        if (maxValue > 1)
            printPartitions(target, maxValue-1, suffix);
        if (maxValue <= target)
            printPartitions(target-maxValue, maxValue, maxValue + " " + suffix);
    }
}

您可以简单地称其为

printPartitions(4, 4, "");

哪个输出

2020-07-28