How to find all subsets in Subset Sum (with Dynamic Programming) in C

Question

I'm new into C (1.5 months studying) and our college professor has asked us to find the Dynamic Programming solution of the Subset Sum problem (along with 2 other ones), but I've followed his instructions and I'm stuck on how to actually find (print) the requested subsets. Can somebody help me understand how this works and how to find all of the subsets?

For the code below, the table is {3,2,1,2,4,3,4,1}, and the subsets need to sum up to 7.

EDIT! --> I modified the initial code so as to find how many subsets exist that sum up to particular value (in our case 7, and the subsets are 20). I repeat that I need help finding all the subsets (combinations) that sum up to a value (7 in this case).

In the above case, this means that the code would be able to print 20 subsets, which are:

Subset 1: 3 2 1 1
Subset 2: 3 2 2
Subset 3: 3 1 2 1
Subset 4: 3 1 3
Subset 5: 3 4
Subset 6: 3 3 1
Subset 7: 3 4
Subset 8: 2 1 4
Subset 9: 2 1 3 1
Subset 10: 2 1 4
Subset 11: 2 2 3
Subset 12: 2 4 1
Subset 13: 2 4 1
Subset 14: 1 2 4
Subset 15: 1 2 3 1
Subset 16: 1 2 4
Subset 17: 2 4 1
Subset 18: 2 4 1
Subset 19: 4 3
Subset 20: 3 4

In the C code that follows I'm able to print the table the instructions want me to, and through this table I must find all the subsets. The instructions for the table were:

x[i][j]=x[i-1][j]; if(j>=y[i-1]) x[i][j]+=x[i-1][j-y[i-1]];

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
long set[] = {3,2,1,2,4,3,4,1};
long sum =7;
long n = sizeof(set)/sizeof(set[0]);
iter_subset_sum(set, n, sum);
return 0;
}

int iter_subset_sum (int *y, long n, long sum) {
  int i,j,k,**x;
  x=malloc((n+1)*sizeof(long**));
  for(i=0;i<=n;i++)
    x[i]=malloc((sum+1)*sizeof(long*));

  for (i=0; i<=n; i++)
    x[i][0] = 1;    
  for (i=1; i<=sum; i++)
    x[0][i] =0;
  for (i=1; i<=n; i++) {    
    for (j=1; j<=sum; j++){
    x[i][j]=x[i-1][j];
    if(j>=y[i-1])
        x[i][j]+=x[i-1][j-y[i-1]];  }   }
  for (i = 0; i <= n; i++){
        for (j = 0; j <= sum; j++)
          printf ("%4d", x[i][j]);
              printf("\n");
      }
      printf("There are %d subsets :", x[n][sum]);
}

Thank you very much in advance!! I would appreciate it very much if you could help a newbie like me that wants slowly to "go deep" into C...

Answer 1

#include <stdio.h>
int iscan(int a[],int n,int sum){
    int f[sum+1],m=0,i,j,k,el,o=0;
    for(i=1;i<=sum;i++)f[i]=0;f[0]=1;
    for(i=0;i<n;i++){
        el=a[i];
        if(el>sum)continue;
        m=m+el>sum?sum:m+el;
        for(k=m-el,j=m;k>=0;j--,k--){
            if(f[k]){
                /* f[j]=el;*/ //old only last conest
                            push_toarray_of_stack(on j position ,item size of el);;//this pseudocode is hint for u homework*********** so and change printing all combination after builing array_of_stack's  of conection

            }
        }
        if(!f[sum])continue;
        k=sum;
        while(k){
            printf("%d ",f[k]);
            k-=f[k];
        }
        printf("%s\n","");
        //exit(0); 
            o++;
    }
    //printf("%s\n","can't");
    return o;
}

int main(){
  int set[] = {1, 3, 2, 4, 2, 6, 5};
  int sum = 5;
  return iscan(set,sizeof(set)/sizeof(set[0]),sum);
}