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

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的序列，现在需要找到Ni的总和。

我的代码：

#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

这个想法基本上是：“ sum如果第一个数字i是从1到的任何数字，sum而数字的其余部分是到，则这些数字求和sum - i。

另外，请注意，您的代码显示了一些改进的空间，例如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不是我的母语，如果您看到更多需要改进的地方，请发表评论。）