Explain sum of subset problem, Find all possible subsets of weight that sum to m, let n =6, m = 30, and w[1:6] = {5, 10, 12, 13, 15, 18).

1. Given positive numbers (weight) w_i where (1<=i<=n) and m.
2. This problem calls for finding all subsets of w_i whose sum is m.
3. For e.g. if n=4, m=31, (w_1,w_2,w_3,w_4) = (11, 13, 24, 7).
4. Then the desired subset are (11, 13, 7) and (2, 4, 7).
5. In this method of giving the solution, the solution vector is given as variable-sized tuple (tuple is collection of element).

6. The solution may also be expressed as fixed size tuple (x_1,x_(2,),x_3,…….,x_n) such that

   x_i =0 if w_i is not selected

   x_i =1 if w_i is selected

7. Using this strategy the solution would be (1,1,0,1) and (0,0,1,1)

Algorithm:

• Let n be the number of elements and let m be the required sum.
• Let w [1…..n] be an array of weights in ascending order and Let x[1….n] be the solution vector.

• Method

  SumOfSubset(s, k, r)
  
  {
  x[k] =1;     //Generating left child
  if(s+w[k]==m)
      Display x[1….k]  //and remaining zeros
  else if(s+w[k]+w[k+1]<=m)
      SumOfSubset(s+w[k], k+1, r-w[k])
  if ((s+r-w[k]>=m) && (s+w[k+1]<=m))
  {
      x [k]=0;
      SumOfSubset(s, k+1, r-w[k]);
  }
  }
  

• S →existing sum
• w[k] → weight of current element
• w[k+1] → weight of next element
• s+w[k] +w [k+1] <=m → sum of existing element+weight of current element+weight of next element is less tham m. -Thus the next element can be selected for time being.
• s+r-w[k]>=m → Even if u discard the current element, you may still get the required sum later on.
• s+w [k+1] <=m → The sum of selected element + weight of next element is less than m . This is even if u take the next element the sum will not exit the required sum(m)
• Thus next element can be selected.

Problem:

n =6, m = 30 and w[6] = {5, 10, 12, 13, 15, 18)

Hence, there are three subset with given sum m=30

A(1011)

B(11001)

C(001001)