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

Question

my problem is quite unique. i am recursively finding powerset of an integer array, after that i am finding the sum of the array, if the sum is a certain number N i look for, it should print the array and stop executing, however, in my case it prints out all the subsets that equal to that N instead of just the first one.

snippet:

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

The results i get are correct, but i only want the first result.

Answer 1

To force the recursion to end early, you can have the powerSet function return a boolean that indicates that the task is completed. After PrintRec is called, powerSet should return true, and if any recursive call returns true, then the caller should immediately return true. That will prevent any additional calls to powerSet and will force the recursion stack to unwind.

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

Note: if you aren't allowed to use <stdbool.h>, then replace bool with int, replace true with 1, and replace false with 0.