Subset Sum-Dynamic Programming

Discover the different techniques used to solve the subset sum problem efficiently.

Dynamic programming algorithm for subset sum problem

Recall that the SubsetSumSubsetSum problem asks whether any subset of a given array X[1..n]X [1 .. n] of positive integers sums to a given integer TT. In the previous lesson, we developed a recursive subset sum algorithm that can be reformulated as follows. Fix the original input array X[1..n]X [1 .. n] and define the boolean function

SS(i,t)=True if and only if some subset of X [i .. n] sums to t.SS(i, t) = True \text{ if and only if some subset of X [i .. n] sums to t.}

We need to compute SS(1,T)SS(1, T). This function satisfies the following recurrence:

SS(i,t)={Trueif t=0Falseif t<0 or i>nSS(i+1,t)  SS(i+1,tX[i])otherwiseSS(i,t)=\begin{cases} & True \hspace{4.72cm} if\space t=0 \\ & False \hspace{4.6cm} if\space t<0\space or\space i>n\\ & SS(i+1,t)\space \vee \space SS(i+1,t-X[i])\hspace{0.4cm} \text{otherwise} \end{cases}

Transforming recurrence into dynamic programming algorithm

We can transform this recurrence into a dynamic programming algorithm following the usual boilerplate.

  • Subproblems: Each subproblem is described by an integer ii such that 1in+11 ≤ i ≤ n + 1 and an integer tTt ≤ T. However, subproblems with t<0t < 0 are trivial, so there’s no point in memoizing them. Indeed, we can modify the recurrence so that those subproblems never arise:

SS(i,t)={Trueif t=0Falseif i>nSS(i+1,t)if t<X[i]SS(i+1,t)  SS(i+1,tX[i])otherwiseSS(i,t)=\begin{cases} & True \hspace{4.72cm} if\space t=0 \\ & False \hspace{4.6cm} if\space i>n\\ & SS(i + 1, t) \hspace{3.75cm} if\space t < X [i] \\ & SS(i+1,t)\space \vee \space SS(i+1,t-X[i])\hspace{0.39cm} \text{otherwise} \end{cases}

  • Data structure: We can memoize our recurrence into a two-dimensional array S[1..n+1,0..T]S[1..n+1,0..T], where S[i,t]S[i,t] stores the value of SS(i,t)SS(i,t).
  • Evaluation order: Each entry S[i,t]S[i, t] depends on, at most, two other entries, both of the form SS[i+1,]SS[i + 1, ·]. So, we can fill the array by considering rows from bottom to top in the outer loop and considering the elements in each row in arbitrary order in the inner loop.
  • Space and time: The memoization structure uses O(nT)O(nT) space. If S[i+1,t]S[i+1, t] and S[i+1,tX[i]]S[i + 1, t − X [i]] are already known, we can compute S[i,t]S[i, t] in constant time, so the algorithm runs in O(nT)O(nT) time.

Here’s the resulting dynamic programming algorithm:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy