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.

Can you show the `arrSum` code? The line `if (arrSum(0, pos, p, 0) == 100)` seems suspicious to me since from the posted code you are calling it with an uninitialized 12 element array where you have only explicitly set the value at location `pos` — pstrjds, Sep 05 '18 at 20:04
The proper declarations for `main` are `int main (void)` and `int main (int argc, char **argv)` (which you will see written with the equivalent `char *argv[]`). **note:** `main` is a function of `type int` and it returns a value. See: [C11 Standard §5.1.2.2.1 Program startup p1 (draft n1570)](http://port70.net/~nsz/c/c11/n1570.html#5.1.2.2.1p1). See also: [See What should main() return in C and C++?](http://stackoverflow.com/questions/204476/) — David C. Rankin, Sep 05 '18 at 20:09
i posted arrSum function, sorry about the confusion, and once again the entire solution is correct, i get valid arrays that their sum is equal to 0, but i only want the first one. @pstrjds — Travis Scott, Sep 05 '18 at 20:19
@DavidC.Rankin nothing much i can do about it, as that's how my professor instructed me to do. — Travis Scott, Sep 05 '18 at 20:24
Are you allowed to change the function declaration of the `powerSet` function, i.e. change the return type or the function arguments? — user3386109, Sep 05 '18 at 21:32
@TravisScott - if you are not on some strange embedded system, then print a copy of the [C11 Standard §5.1.2.2.1 Program startup p1 (draft n1570)](http://port70.net/~nsz/c/c11/n1570.html#5.1.2.2.1p1) take it to him (or her) and ask why? If they can't answer, drop the class (you still have time) and re-enroll with another professor. — David C. Rankin, Sep 06 '18 at 00:21
while the returned type from `main(()` is always `int`. There are some (WAY BEHIND) compilers, like Visual Studio, that will accept invalid code without outputting a message complaining about the return type — user3629249, Sep 07 '18 at 01:07

score 2 · Accepted Answer · answered Sep 05 '18 at 21:52

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.

Splendid! that worked perfectly, thank you very much. I used int instead of bool. — Travis Scott, Sep 05 '18 at 22:00

score 1 · Answer 2 · answered Sep 05 '18 at 20:07

It's because the call stack is full of powerset-function executions that will all be brought to an end, each having the chance to enter print without the chance to detect that it has been called before.

You could introduce a "shared counter" that is incremented once print is called. Share this counter by, for example, passing it by reference to all the calls:

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

This solution would probably work, but is there a more elegant way to solve the problem? or is it the fact that my function is built the way it is? — Travis Scott, Sep 05 '18 at 20:20

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

2 Answers2