subset sum

general
1

Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the
numbers such that they sum up to (hit)??

can any one plz explain this code???
and what r the changes required to print those subset???

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
int m[30000],a[21];
int main()
{
    int t,N,M,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]);
        for (i=0;i<=M;i++)
            m[i]=0;
       	m[0]=1;
        for(i=0; i<N; i++)
        	for(j=M; j>=a[i]; j--)
        		m[j] |= m[j-a[i]];
  		if (m[M])
  		   printf("Yes\n");
	   else
	       printf("No\n");
    }
}
2

With each element in the array we are finding out what all subset sums are possible. Lets take an example 2, 3, 5. If you consider only first element ‘2’ we can achieve only one sum which is 2. If you consider first two elements ‘2’ and ‘3’ we can achieve sums 2, 3, 5(2+3). If you consider first three elements ‘2’, ‘3’ and ‘5’ we can achieve sums 2, 3, 5(2+3), 7(2+5), 8(3+5), 10(2+3+5).

In the above code, array m is filled with ‘1’ whose sums can be achieved. At the end 'M’th index of array m is true then sum ‘M’ can be achieved, otherwise not.(Note: m[0] is true because sum ‘0’ is always achieved)

1 Like
3

what does this statement do " m[j] |= m[j-a[i]]; "???

4

the sum ‘j’ can be reached if it is already OR if ‘j-a[i]’ can be reached (and then you’ll have to add a[i] to the subset).

5

Consider this example

N = 3 M = 10

Elements are 2 , 4 , 5

Initially set all elements to 0 , i.e, m[0…10] = 0

what is m?

m[ x ] = 1 if x can be formed by selecting a subset of n and adding them, else it is 0

set m[0] = 1 , You can always make 0 by selecting none.

so now the array looks like 1 0 0 0 0 0 0 0 0 0

Now take one element from n

Take “2” …
If for any x , if m[x] == 1 , then this “2” can be added to that value to make a sum of x+2

This statement m[x] = m[x] | m[x-n[i]] does that … if m[x] is already 1 or m[x-n[i]] is 1 , then set m[x] to 1

so now the array looks like 1 0 1 0 0 0 0 0 0 0 0

Take “4”

You can add it to 0 and make 4, or add it to 2 and make 6

so now the array looks like 1 0 1 0 1 0 1 0 0 0 0

Take “5”

0 + 5 = 5

2 + 5 = 7

4 + 5 = 9

6 + 5 = 11( we dont need this ,we need <= 10 )

Finally Array is

1 0 1 0 1 1 1 1 0 1 0

One last point notice for(j=M; j>=a[i]; j–) , It runs from right to left in array (higher to lower) , This is to avoid reusing the same element twice.

2 Likes
6

just wanting to know if we can modify the above code to find these subset?
thankx in advance…