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

Question

我正在解决一个编程练习,并遇到了一个问题,我无法满意地找到解决方案.问题如下:

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然后输出应为输出=

  1 1 1 1
  1 1 2
  2 2
  1 3
  4

我该如何考虑解决这个问题？我想知道使用递归.任何人都可以为我提供这个问题的算法吗？或暗示解决方案.对这类问题的任何解释都是受欢迎的.(我是编程世界的初学者)谢谢!!

Answer 1

我会这样接近它:

首先,概括问题.您可以定义一个功能

printPartitions(int target, int maxValue, string suffix)

与规格:

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

请注意,始终至少有一个解决方案(前提是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, "");

哪个输出

1 1 1 1 
1 1 2 
2 2 
1 3 
4