The subset-sum problem is defined as follows. Given a set of n positive…

Recurrence: For 2 ≤ i ≤ n and ai ≤ j ≤ W, the correct recurrence is X[i, j] = X[i-1, j] OR X[i-1, j - ai].

Reasoning:

• If there is a subset of the first i-1 elements that sums to j, then X[i-1, j] is TRUE and so X[i, j] is TRUE (we do not use ai).

• If there is a subset of the first i-1 elements that sums to j - ai, then by including ai we obtain a subset of the first i elements that sums to j, so X[i-1, j - ai] being TRUE makes X[i, j] TRUE.

Note: using X[i, j - ai] (from the same row i) would allow using ai multiple times, which is not allowed in the subset-sum (0/1) formulation.

Base cases:

• For all i, X[i, 0] = TRUE (the empty subset sums to 0).

• For j > 0 and i = 1, X[1, j] is TRUE only if a1 = j (otherwise FALSE).

• If you index rows from 0 (with 0 elements), then set X[0, 0] = TRUE and X[0, j>0] = FALSE.

Algorithm and complexity:

• A straightforward DP fills the table X for i = 1..n and j = 0..W using the recurrence above in O(nW) time and O(nW) space.

• Space can be reduced to O(W) by keeping only the previous row X[i-1, ·] when computing the current row.

Conclusion: The correct recurrence for 2 ≤ i ≤ n and ai ≤ j ≤ W is X[i, j] = X[i-1, j] OR X[i-1, j - ai].