Hello,

I am working on a homework lab in which we have to find all the subsets equal to a given sum from an array of numbers.

For example, an array of 7 numbers (1, 3, 4, 6, 7, 10, 25) with a sum of 25 would be (1, 3, 4, 7) and (25)

We are supposed to use dynamic programming to solve this.

Now using the code below that we went over in class (Sedgewick's subsetSum), I understand how to this finds the first subset that adds up to the sum given. What's stumping me is how to find multiple subsets.

For example if given the set I listed earlier (1, 3, 4, 6, 7, 10, 25) and sum of 25, the output I would need to give would be as follows:Code:main(){ // Get input sequence int n; // Size of input set int m; // Target value int *S; // Input set int *C; // Cost table int i,j,potentialSum,leftover; scanf("%d",&n); scanf("%d",&m); S=(int*) malloc((n+1)*sizeof(int)); C=(int*) malloc((m+1)*sizeof(int)); if (!S || !C) { printf("malloc failed %d\n",__LINE__); exit(0); } S[0]=0; // Sentinel zero for (i=1;i<=n;i++) scanf("%d",S+i); // Initialize table for DP C[0]=0; // DP base case // For each potential sum, determine the smallest index such // that its input value is in a subset to achieve that sum. for (potentialSum=1; potentialSum<=m; potentialSum ++) { for (j=1;j<=n;j++) { leftover=potentialSum-S[j]; // To be achieved with other values if (leftover<0) // Too much thrown away continue; if (C[leftover]==(-1)) // No way to achieve leftover continue; if (C[leftover]<j) // Indices are included in break; // ascending order. } if (j<=n) C[potentialSum]=j; else C[potentialSum]=-1; } /**/ // Output the input set printf(" i S\n"); printf("-------\n"); for (i=0;i<=n;i++) printf("%3d %3d\n",i,S[i]); // Output the DP table printf(" i C\n"); printf("-------\n"); for (i=0;i<=m;i++) printf("%3d %3d\n",i,C[i]); /**/ if (C[m]==(-1)) printf("No solution\n"); else { printf("Solution\n"); printf(" i S\n"); printf("-------\n"); for (i=m;i>0;i-=S[C[i]]) printf("%3d %3d\n",C[i],S[C[i]]); } }

Solution with 1 elements

i S

-------

7 25

No solution with 2 elements

No solution with 3 elements

No solution with 4 elements

Solution with 5 elements

i S

-------

6 10

5 7

3 4

2 3

1 1

No solution with 6 elements

No solution with 7 elements

Can anyone give me an idea of which direction to go on this? In class the teacher said it would be mainly just modifying the code we went over in class. Any input would be appreciated. Not asking for anyone to code this/do this for me, but just give me any ideas on where to start on this.

Thanks!