recursion process in a void function

Question

I just found a subset sum code snippet(python) in stackoverflow. Due to fascination, I translated the code snippet to C language(a mistake of course).

My code snippet

#include <stdio.h>
#include <stdlib.h>

int top = 0;

void print(int *partial)
{
        int j =0;
        while(partial[j] != 0)
        {
                printf("%d ",partial[j]);
                j++;
        }
}
void subset(int *nos,int *partial,int reqvalue,int maxvalue) {
        int par_sum = 0,i = 0,count=0;
        while(partial[i] != 0)
        {
                par_sum += partial[i];
                i++;
        }

        if(par_sum == reqvalue)
        {
                print(partial);

        }
        if(par_sum > reqvalue)
        {
                 return ;
        }
        while(nos[count]!= 0)
        {
                count++;
        }
        for(int j =0; j < count; j++)
        {
                  int n;
                  int remaining[count+1];
                  n = nos[j];
                  for(int k = j+1; k < count+1; k++) {
                        remaining[k-(j+1)] = nos[k];
                  }
                  partial[top] = n;
                  top++;
                  subset(remaining,partial,reqvalue,maxvalue);
                  top--;
        }

}
int main()
{
        int reqvalue,no_count,sum = 0;
        int *nos;
        int *partial;
        scanf("%d %d",&reqvalue,&no_count);
        nos = calloc(( no_count+1),sizeof(int));
        partial = calloc(no_count, sizeof(int));
        for(int i =no_count-1; i>=0; i--)
        {
                scanf("%d",&nos[i]);
                sum += nos[i];

        }
        subset(nos,partial,reqvalue,sum);
        return 0;
}

#Input
#100 10
#4 14 15 18 29 32 36 82 95 95

#Output
#82 18 82 14 4 82 14 4 36 32 18 14

I'm just wondering, how can I print only the first subset instead of printing all subsets?
How can I break immediately from the recursion mechanism after printing the first subset ?
Expected Output

82 18

Original python snippet

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Thanks in advance

Yuri Feldman · Answer 1 · 2020-02-02T08:22:56.260

Assuming the translation to c is correct, you only output the subset in the clause

if(par_sum == reqvalue)
    print(partial);

Hence to print only the first one you can return at the end of this clause, and make sure that the for loop breaks as well, e.g. by using subset's return code (changing it to int, for example), like so:

#define BREAK_LOOP 1    // before subset 

int subset(int *nos,int *partial,int reqvalue,int maxvalue) 
{
...

Modify the output clause to return BREAK_LOOP and return 0 in the other case:

if(par_sum == reqvalue)
{
    print(partial);
    return BREAK_LOOP; 
}        

if(par_sum > reqvalue)
    return 0;

Modify the for loop to check subset return value, and return 0 otherwise.

int subset_ret_val = 0; 
for(int j =0; j < count; j++)
{
   ...
   subset_ret_val = subset(remaining,partial,reqvalue,maxvalue);
   if (subset_ret_val)
       return subset_ret_val; 
   top--;
}
return 0;

If you can/would not change the function's return type to int, you can equivalently pass another pointer argument. If you cannot modify the function signature at all, you can still probably do some hack abusing existing arguments, but you did not seem to request a solution for that.

recursion process in a void function

1 Answers1