Thread: Find all subsets with sum of x

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.

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

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:

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!

Read this, and see if it helps. There is a section on dynamic programming to solve it, as well.

Subset sum problem - Wikipedia, the free encyclopedia