c - 数组的整数子集的总和，获取所有结果而不是第一个

Question

我的问题很独特。我正在递归地查找整数数组的幂集，之后我找到数组的总和，如果总和是我要查找的某个数字 N ，它应该打印数组并停止执行，但是，在我的例子中它打印出来所有等于该 N 的子集，而不仅仅是第一个。

片段:

void main()
{
    char a;
    int arr[] = { 1, 4, 15, 20, 1, 1, 2, 3, 66, 14, 33 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int temp[12];
    powerSet(arr, temp, n, 0, 0);

    scanf("%c", &a);
}
void powerSet(int* arr, int* p, int n, int pos, int index)
{
    if (index >= n)
    {
        return;
    }
    p[pos] = arr[index];
    if (arrSum(0, pos, p, 0) == 100)
    {
        PrintRec(0, pos, p);
        return;
    }
    else
    {
        //Most likely an issue here.
        powerSet(arr, p, n, pos + 1, index + 1);
        powerSet(arr, p, n, pos, index+1);
    }
}
void PrintRec(int j, int end, int* p)
{
    if (j > end)
    {
        printf("\n");
        return;
    }
    printf("%d ", p[j]);
    PrintRec(j + 1, end, p);
}

总和:

int arrSum(int j, int end, int* p, int sum)
{
    if (j > end)
    {
        return sum;
    }
    arrSum(j + 1, end, p, sum +=p[j]);
}

我得到的结果是正确的，但我只想要第一个结果。

Answer 1

要强制递归提前结束，您可以使用 powerSet函数返回一个 bool 值，表示任务已完成。在PrintRec之后被称为，powerSet应该返回 true ，如果任何递归调用返回 true , 那么调用者应该立即返回 true .这将阻止对 powerSet 的任何额外调用并将强制递归堆栈展开。

#include <stdbool.h>

bool powerSet(int* arr, int* p, int n, int pos, int index)
{
    if (index >= n)
    {
        return false;
    }
    p[pos] = arr[index];
    if (arrSum(0, pos, p, 0) == 100)
    {
        PrintRec(0, pos, p);
        return true;
    }
    else
    {
        if (powerSet(arr, p, n, pos + 1, index + 1))
            return true;
        if (powerSet(arr, p, n, pos, index+1))
            return true;
    }
    return false;
}

注意:如果您不允许使用 <stdbool.h> , 然后替换 bool与 int , 替换 true与 1 , 并替换 false与 0 .