The subset-sum problem is defined as follows. Given a set of n positive…
2008
The subset-sum problem is defined as follows. 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? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. 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. Which of the following is valid for 2 <= i <= n and ai <= j <= W?
- A.
X[i, j] = X[i − 1, j] V X[i, j − ai]
- B.
X[i, j] = X[i − 1, j] V X[i − 1, j − ai]
- C.
X[i, j] = X[i − 1, j] ∧ X[i, j − ai]
- D.
X[i, j] = X[i − 1, j] ∧ X[i − 1, j − ai]
Attempted by 81 students.
Show answer & explanation
Correct answer: B
Concept
In a subset-sum feasibility table, X[i, j] records whether some subset of the first i items sums to exactly j. Because each item may be used at most once, the transition for item i must look only at row i − 1 (results built from the first i − 1 items) in BOTH the ‘exclude item i’ and ‘include item i’ cases — referencing row i itself would let item i be reused.
Application
Exclude item i: a subset of the first i − 1 items already sums to j, so X[i, j] is true via the term X[i − 1, j].
Include item i (valid only when ai ≤ j): a subset of the first i − 1 items sums to j − ai, so adding item i reaches j — the term X[i − 1, j − ai].
Combine with OR: X[i, j] = X[i − 1, j] V X[i − 1, j − ai] for 2 ≤ i ≤ n and ai ≤ j ≤ W. (not AND — either path alone is enough to make j reachable, so requiring both would wrongly reject valid sums).
Base cases: X[i, 0] = TRUE for every i (the empty subset sums to 0); X[1, j] = TRUE only when j = a1, otherwise FALSE.
Cross-check
Take S = {a1 = 2, a2 = 3} and W = 6. The only subsets are {}, {2}, {3}, {2, 3}, with sums 0, 2, 3, 5 — so 6 is NOT achievable and X[2, 6] must be FALSE.
With the row-(i − 1) recurrence: X[2, 6] = X[1, 6] V X[1, 3] = FALSE V FALSE = FALSE. Correct.
If the include-case instead referenced the SAME row (X[2, 6] = X[1, 6] V X[2, 3]), then X[2, 3] itself — computed the same flawed way — equals X[1, 3] V X[2, 0] = FALSE V TRUE = TRUE (using the base case X[2, 0] = TRUE), which makes X[2, 6] evaluate to TRUE. That is wrong: it counts item a2 = 3 twice (3 + 3 = 6), which is exactly the reuse bug a same-row reference introduces.
A parallel check rules out combining the two branches with AND instead of OR. Take S = {a1 = 2, a2 = 1} and W = 3: the subset {2, 1} sums to 3, so X[2, 3] must be TRUE. With the correct OR-combination, X[2, 3] = X[1, 3] V X[1, 2] = FALSE V TRUE = TRUE — correct. Replacing OR with AND gives X[2, 3] = X[1, 3] ∧ X[1, 2] = FALSE ∧ TRUE = FALSE, which is wrong: AND forces both the 'excluded' and 'included' cases to hold at once, so it misses sums reachable through only one of the two routes.
Result
The valid recurrence for 2 ≤ i ≤ n and ai ≤ j ≤ W is X[i, j] = X[i − 1, j] V X[i − 1, j − ai].