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

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);
}

arr总和：

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-函数执行都会结束，每一次都有机会进入print而没有机会检测到自己已经之前打过电话。

您可以引入一个 "shared counter"，一旦 print 被调用就会递增。共享此计数器，例如，通过引用将其传递给所有调用：

int main() {
    int printCounter=0;
    powerSet(...., &printCounter);
}

void powerSet(int* arr, int* p, int n, int pos, int index, int *counter) {
   ...
   if(!*counter) {  // this block avoids that print will be called more than once
      print(...);
      (*counter)++;
   }
   ...
   powerSet(...., counter);

Answer 2

要强制递归提前结束，您可以让 powerSet 函数 return 一个表示任务已完成的布尔值。 PrintRec被调用后，powerSet应该returntrue，如果任何递归调用returns true，那么调用者应该立即return 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.

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

sum of integer subset of an array, getting all results instead of first one

c

arrays

recursion

sum

powerset