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

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

请尝试向我解释你的思维方式，以及你如何处理这种问题，我想成为史无前例的最佳:(.....

- Zamkie

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语言不是我的母语，如果您发现更多需要改进的地方，请评论。）

- tobias_k

---

非常感谢您清晰的回答！ 我明白你在那里做了什么，希望下一次我能够自己做到这一点。 这种问题对我来说太难了 :/ - Zamkie