C - 递归 - 数据结构课程 - 打印所有可能的系列

Question

>我需要打印所有可能的总和等于 N 的系列; 例如是 n == 4，输出应该是：

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

我解决这个问题的思路是： 打印数字 i 不在系列中的系列 打印序列中数字i的序列，现在需要找到N-i的总和。

我的代码：

#include <stdio.h>
#include <stdlib.h>
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
printf(" %d ", arr[i]);
}
printf("n");
}
void printAllHelper(int* a,int size, int sum, int used,int index) {
if (sum == 0) {
a -= used;
printArr(a, used);
}
else if (sum < 0 || index == size) 
{
return;
}
else {
for(int i = 1 ; i <= size ; i ++) 
{
printAllHelper(a, size, sum, used, index + 1);
if (i <= sum)
{
*a = i;
}
printAllHelper(a+1, size, sum -i, used +1, index + 1);

}


}
}
void printAll(int num) {
int* myArray = (int*)malloc(num * sizeof(int));
printAllHelper(myArray,num,num,0,0);
}
void main() {
printAll(4);
}

我的输出：

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

请试着向我解释你的思维方式，以及你如何处理这种问题，我想成为最好的，就像没有人:(一样......

Answer 1

你的推理不太正确，但你的代码几乎是正确的。else部分中的循环应该是

for(int i = 1 ; i <= sum ; i ++)  {
*a = i;
printAllHelper(a+1, size, sum-i, used+1, index+1);
}

有了这个，我得到了输出

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

这个想法基本上是："如果第一个数字i是从1到sum的任何数字，其余数字的总和是sum - i，则数字的总和为sum。

另外，请注意，您的代码显示出一些改进的空间，例如used和index变量似乎有点多余。并且不添加大于sum或小于1的数字，检查是否sum < 0 || index == size也没有必要。因此，您也不需要size参数。您的printAllHelper可以简化为如下所示：

void printAllHelper(int* a, int sum, int index) {
if (sum == 0) {
printArr(a, index);
} else {
for(int i = 1 ; i <= sum ; i++)  {
a[index] = i;
printAllHelper(a, sum-i, index+1);
}
}
}

(注意：C不是我的母语，如果你看到更多需要改进的地方，请评论。