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

Answer will be both option A and C.

See the solution here with proper visualisation - https://www.youtube.com/watch?v=8_AYhj_v7Y0

---

✅ Correct answer: C. X[n,W]

Explanation:

• X[i][j] tells us if we can form sum j using the first i elements.

• So X[n][W] checks if we can form sum W using all n elements.

• If it's TRUE, then some subset of the full set adds up to W.

That’s exactly what the question is asking.

---

• Why  others are wrong:

• Option A: X[1, W]

  • Translation: "Is there a subset of just the very first element $\{a_1\}$ that sums to $W$?"

  • Why it's wrong: This only tells you if the first element is exactly equal to $W$. It completely ignores the other $n-1$ elements in the set, failing to solve the general problem.

• Option B: X[n, 0]

  • Translation: "Is there a subset of all $n$ elements that sums to $0$?"

  • Why it's wrong: In the subset sum problem, you can always achieve a sum of $0$ by picking the empty subset. This entry will mathematically always be TRUE, but it provides absolutely zero information about whether you can achieve the actual target sum $W$.

• Option D: X[n-1, n]

  • Translation: "Is there a subset of the first $n-1$ elements that sums to a target value equal to $n$ (the count of elements)?"

  • Why it's wrong: This is a deliberate distractor mixing up variables. The target sum we care about is $W$, not the count of elements $n$. Evaluating a target sum of $n$ is irrelevant to the question asked.

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

@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. 

---

Yes so that means A is right too isn't it?

---

@Sidd1425 noo its a specific example but algorithm should work on any input so for bigger values it can't be true as entry $1,W$ will tell us only first element of array and sum $W$ which may or may not be true so ultimatley we can't say this should be ans of all elements may be after that we can find that susbet 

Answer 2

The answer should be A, C.

The recerruence of subset problem is: X[i,j] = X[i-1,j] or X[i-1, j-ai]. From this it is very clear that X[n,W](which repersents the existence of a subset with sum to W) is always true if X[i,W] is true for any 0 < i < n.

Hence Option A implies Option C. Both are correct answers.

Comments

Yes because p->q
p: X[1][W] is true means, with one a ∈ S, we can achieve the required sum.Thus we cant make the consequent(q) False in this case.
So I too think that option A should be correct.

Answer 3

Here it is : 
Enjoy this : 

Answer 4

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.