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

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.