生成数字的所有不同分区

Question

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

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

我认为递归方法应该有效,但我无法处理不同元素的附加约束.将非常感谢C/C++/Java中的伪代码或示例代码.

谢谢!

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

Answer 1

我草拟了这个解决方案（它可以美化和优化），它不应该生成重复项：

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);
    }
}