GATE 2008 CS – Question 80
Given positive integers $S=\{a_1,\ldots,a_n\}$ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns (1≤i≤n, 0≤j≤W), is true iff a subset of the first i elements sums to j. For $2\le i\le n$ and $a_i\le j\le W$, which is valid?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $X[i,j]=X[i-1,j]\lor X[i-1,j-a_i]$
Explanation
We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort