сумма целого подмножества массива, получая все результаты вместо первого

Question

моя проблема совершенно уникальна. я рекурсивно нахожу powerset целочисленного массива, после этого я нахожу сумму массива, если сумма - это определенное число 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);
}

arrSum:

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 возвращать логическое значение, указывающее, что задача выполнена. После вызова 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.

Answer 2

Это потому, что стек вызовов полон powerset -функций выполнения, которые все будут доведены до конца, и у каждого есть шанс ввести print без возможности обнаружить, что он был вызван ранее.

Вы можете ввести «общий счетчик», который увеличивается при вызове 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);