递归-数据结构课程-打印所有可能的系列
recursion - data structure course - print all possible series
我需要打印所有可能的序列，它们的总和等于 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
请尝试向我解释你的思维方式，以及你如何处理这类问题，我想成为最优秀的人:(.....
你的推理不太正确，但你的代码几乎是正确的。 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
思路基本上是："The numbers sum to sum if the first number i is any number from 1 to sum and the rest of the numbers sum to 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 不是我的母语，如果您看到更多需要改进的地方，请发表评论。）
我需要打印所有可能的序列，它们的总和等于 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
请尝试向我解释你的思维方式，以及你如何处理这类问题，我想成为最优秀的人:(.....
你的推理不太正确，但你的代码几乎是正确的。 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
思路基本上是："The numbers sum to sum if the first number i is any number from 1 to sum and the rest of the numbers sum to 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 不是我的母语，如果您看到更多需要改进的地方，请发表评论。）