GATE CSE 2008 | Question: 81

Question

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows and $W+1$ columns. $X[i, j], 1 \leq i \leq n, 0 \leq j \leq W$, is TRUE, if and only if there is a subset of $\{a_1, a_2, \dots, a_i\}$ whose elements sum to $j$.

Which entry of the array $X$, if TRUE, implies that there is a subset whose elements sum to $W$?

• A. $X[1, W]$
• B. $X[n, 0]$
• C. $X[n, W]$
• D. $X[n-1, n]$

Comments

In option (D), Subset whose elements sum to W only exists if n = W.

Answer 1

ANSWER is C.

If LAST ROW and LAST COLUMN entry is $1$, then there exists a subset whose elements sum to $W$.

Comments

shouldnot answer be A)?

---

here question told " 2-dimensional Boolean array "

and array has n rows and W+1 column

So, from here we  can say each row contain W+1 elements

and it is a boolean array,

So, array only contain 0 or 1

So, sum of 1 row can be maximum W+1

And question asking for " there is a subset " whose sum is W

So, isnot 1 row and W column will be possible answer?

Which is option A)

Where am I going wrong?

---

^ read the following two lines of the given question carefully.

1.Given a set of n positive integers, S={a1,a2,a3,…,an}, and positive integer W, is there a subset of S whose elements sum to W.

2.X[i,j], 1≤i≤n,0≤j≤W, is TRUE, if and only if there is a subset of {a1,a2,…,ai} whose elements sum to j.

---

Option A says if only first number is = W. that is X[1][W] = 1.

---

right @vijay (y)

Here 2 D array definition changed

According to point 1)there a subset of S whose elements sum to W. i.e. ok.

but in point 2) .X[i,j], 1≤i≤n,0≤j≤W, is TRUE, if and only if there is a subset of {a1,a2,…,ai} whose elements sum to j.

So, sum of elements is j, so sum could be less than W too.

How do u predict it will be W?

---

* So, sum of elements is j, so sum could be less than W too. - Yes.

* X[i,j], 1≤i≤n,0≤j≤W.

here we are supposed to take array elements from a1 to ai only ..and among these numbers, we have to check if subset sum = j or not ..

but In the definition of W we can use elements from a1 to a_n .... so here no of array elements to be used in the calculation of subset sum differs ..

---

then what is meaning of

2-dimensional Boolean array, X, with n rows and W+1 columns

Say an array X[3,2]={1,2,3}

i should be always less than j

but is it has W+1 columns?

---

here in 2-D array, row tells ( say X[p][q]) the domain that we are supposed to use in the given array in the calculation of subset sum.. here we will be using elements from a[1] to a[p] only not a[p+1] or a[p+2] ... if total elements in given array = n ..so we can use maximum n elements ..that's why row (max) = n = no of elements of given array.

X[p][q] -> subset sum = q or not ..where elements used in calculation of subset sum = a[1] , a[2] , ....a[p] ..

now coming to the the column -

here column says what is the value of desired subset sum ..min = 0 and max = W ( so total column = W+1) .. 

---

 your example- Say an array X[3,2]={1,2,3}.

here given array = a = {1, 2, 3}

X[3,2] = > can we have subset sum =2 in array = { 1, 2, 3} ...[ see here p = 3 ..so using all elements ]

X[3,2] = should be 1 , since subset sum = 2 is there [ take only 2nd element of array ]

---

@vijaycs

1)  X[p][q] ={a[1],a[2],...............a[p]}

Only upto a[p] elements are possible,not more than that.

Say in worst case W=5

then is there 6 column possible?

2)" Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W? "

but if there is more than one subset sum=5, will it be accepted?

---

1.

Say in worst case W=5

then is there 6 column possible?

----> yes total 6 column ..but no need of 7th column in the calculation of subset-sum =5. 

  1st column will be for subset-sum =0
 2nd column will be for subset-sum =1

.
. 6th -------------------------------------- = 5.
 

---

2 . but if there is more than one subset sum=5, will it be accepted?

----> yes .. any one possible subset will make X[ ] [5] = 1.
 

---

how 6 column possible?

S contains only 3 elements

S={1,2,3}

And W=5 possible here.

But column W+1 not possible

---

W+1 columns are there to accommodate col with W=0. Suppose there are 3 elements {1,2,3} and required sum=5(W).

So, n rows( 3 rows) and 6 columns(W+1) in a way like below:

                         0 1 2 3 4 5

                     1                

                     2                 

                    3                 (nW)

For here, we can see that the value of nW will give us the subset sum.

---

See this will be the algo for it

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,j,m,n,W,sum,s[10][10],flag;
    printf("Number of elements in array:");
    scanf("%d%d",&n,&W);
    printf("Enter values in array either 0 or 1:");
    for(i=0;i<n;i++)
    {
        for(j=0;j<W;j++)
        {
             printf("Enter the a[%d][%d]element:",i,j);
             scanf("%d",&s[i][j]);
        }
    }
    for(i=0;i<=n;i++)
    {
         sum=0;
         for(j=0;j<W;j++)
         {   
             if(s[i][j]==1)
             {
                 if(sum!=W)
                 {
                 sum=sum+1;
                 if(sum==W)
                 {
                     flag=1;
                     break;
                 //printf("The sequence is S[%d][%d]",i,j);
                 }
                 }
             }
             else
             {
                 if(s[i][j]==0)
                 continue;
                 else
                 break;
             }
         }
     }
     if(flag==1)
     {
        printf("Such a sequence exists");
     }
     else
     {
         printf("Such a sequence not exists");
     }
        
   system("pause");
   return 0;
}            

---

Here is nice explaination.

---

Question description itself gives the answer :)

---

@srestha Ma'am, Consider the following set $S =  \{ 1, 2, 3, 4, 5 \} \space and \space W = 1 $

What would be then stored at $X[1,1] \space ( i.e \space X[1,W] ) \space and \space X[5,1] \space (i.e \space X[n,W])  $ 

Wouldn't both of them be $= True$ as we have $ S_1 = \{1\} $ for $i=1$ and when $i=5 \space i.e$ $S_2 = \{1,2,3,4,5\} $ the subset would be one containing the first element i.e 1 in this case. 

Answer 2

The answer is C.  Because of entry X[n,w] is true only when there is a subset of N integer whose sum is W.