Official PYQ · 2008Q80Algorithm Design: Dynamic ProgrammingMCQ1 mark

GATE CS 2008 Q80 — Algorithm Design: Dynamic Programming

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 of the following is valid for $2 \leq i \leq n$ , and $a_i \leq j \leq W$ ?

View worked solution

Answer: B

To find the recurrence relation for $X[i, j]$ , we analyze the choices available for the element $a_i$ when trying to form a subset of the first $i$ elements, $\{a_1, a_2, \dots, a_i\}$ , that sums to $j$ :

Exclude $a_i$ : If we do not include $a_i$ in the subset, we must form the sum $j$ using only the first $i-1$ elements. This is possible if and only if:
$X[i-1, j] = \text{TRUE}$

Include $a_i$ : If we include $a_i$ in the subset (which is allowed since $a_i \le j$ ), the remaining sum to be formed is $j - a_i$ . This remaining sum must be formed using the first $i-1$ elements. This is possible if and only if:
$X[i-1, j-a_i] = \text{TRUE}$

Since the subset-sum problem allows each element to be chosen at most once, and the overall problem is solvable if either of the two choices is successful, we combine them using the logical OR ( $\vee$ ) operator:

X[i, j] = X[i-1, j] \vee X[i-1, j-a_i]

Thus, Option B is the correct recurrence relation.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Algorithm Design: Dynamic Programming questions

GATE CS 2008 Q80 — Algorithm Design: Dynamic Programming

Related questions