c - 生成数字的所有不同分区

Question

我正在尝试编写一个 C 代码来生成所有可能的分区(分为 2 个或更多部分)，其中包含给定数字的 distinct 元素。给定分区的所有数字的总和应等于给定的数字。例如，对于输入 n = 6，具有 2 个或更多具有不同元素的元素的所有可能分区是:

• 1, 5
• 1、2、3
• 2, 4

我认为递归方法应该可行，但我无法处理不同元素的附加约束。非常感谢使用 C/C++/Java 编写的伪代码或示例代码。

谢谢!

编辑: 如果它使事情变得更简单，我可以忽略至少有 2 个元素的分区的限制。这将允许将数字本身添加到列表中(例如，6 本身将是一个微不足道但有效的分区)。

Answer 1

你根本不需要递归。数字列表本质上是一个堆栈，通过按顺序迭代可以确保没有重复。

这里有一个版本说明了我的意思(你标记了这个 C，所以我用 C 写了它。在 C++ 中，你可以使用带有推送和弹出的动态容器，并大大整理它)。

#include <stdio.h>
#include <stdlib.h>

void partition(int part)
{
int *parts;
int *ptr;
int i;
int idx = 0;
int tot = 0;
int cur = 1;
int max = 1;

    while((max * (max + 1)) / 2 <= part) max++;

    ptr = parts = malloc(sizeof(int) * max);

    for(;;) {
        if((tot += *ptr++ = cur++) < part) continue;

        if(tot == part) {
            for(i = 0 ; i < ptr-parts ; i++) {printf("%d ",parts[i]);}
            printf("\n");
        }

        do {
            if(ptr == parts) {free(parts); return;}
            tot -= cur = *--ptr;
        } while(++cur + tot > part);
    }
}

int main(int argc, char* argv[])
{
    partition(6);
    return 0;
}