我试图写一个C代码来生成与给定数目的不同元件的所有可能的分区（成2个或更多份）。 给定分区的所有号码的总和应等于给定数。 例如，对于输入n = 6 ，具有2个或更多个元件以不同的元件的所有可能的分区是：
我认为一个递归方法应该可行，但我不能把不同元素的添加约束的照顾。 伪码或C / C ++ / Java中的示例代码将不胜感激。
谢谢！
编辑：如果它使事情变得更容易，我可以忽略具有至少2个元素分区的限制。 这将使数字本身将被添加到列表（例如，6本身将是一个微不足道的，但有效的分区）。
我勾画该溶液（它可以美化和优化）不应该产生重复：
void partitions(int target, int curr, int* array, int idx)
{
if (curr + array[idx] == target)
{
for (int i=0; i <= idx; i++)
cout << array[i] << " ";
cout << endl;
return;
}
else if (curr + array[idx] > target)
{
return;
}
else
{
for(int i = array[idx]+1; i < target; i++)
{
array[idx+1] = i;
partitions(target, curr + array[idx], array, idx+1);
}
}
}
int main(){
int array[100];
int N = 6;
for(int i = 1; i < N; i++)
{
array[0] = i;
partitions(N, 0, array, 0);
}
}
你正在试图做不会使很多意义，我，但这里是我会怎么处理它。
首先，我想创建一个循环，迭代i从1到n - 1.在第一循环中，您可以添加分区1，我。 然后，我使用的值去递归i得到一切，也可以添加到1子分区。
再继续2，依此类推。
首先，写一个递归算法返回的所有分区，包括那些包含重复。
其次，编写消除了包含重复的元素分区的算法。
编辑：
您可以通过避免使对已经看到数字递归调用避免重复的结果。 伪代码：
Partitions(n, alreadySeen)
1. if n = 0 then return {[]}
2. else then
3. results = {}
4. for i = 1 to n do
5. if i in alreadySeen then continue
6. else then
7. subresults = Partitions(n - i, alreadySeen UNION {i})
8. for subresult in subresults do
9. results = results UNION {[i] APPEND subresult}
10. return results
编辑：
您还可以防止产生相同的结果超过一次。 通过修改环路的范围，让你只有在一个单调递增的方式增加新的元素做到这一点：
Partitions(n, mustBeGreaterThan)
1. if n = 0 then return {[]}
2. else then
3. results = {}
4. for i = (mustBeGreaterThan + 1) to n do
5. subresults = Partitions(n - i, i)
6. for subresult in subresults do
7. results = results UNION {[i] APPEND subresult}
8. return results
你根本不需要递归。 号码列表本质上是一个堆栈，并以迭代可以确保没有重复。
这里有一个版本，这显示了我的意思（你这个标记C，所以我写了它在C.在C ++中，你可以使用一个动态容器push和pop，整洁这件事相当）。
#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;
}
