Project ForgeAlgorithms
Dynamic Programming & Greedy Algorithms
GATE 2008
Medium
(Continuing the subset-sum DP array X[i,j], 1≤i≤n, 0≤j≤W.) Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
- AX[1,W]
- BX[n,0]
- X[n,W]
- DX[n-1,n]
Explanation
X[n,W] being TRUE means: a subset of ALL n elements sums to exactly W — precisely the answer to the subset-sum problem being asked.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.