Course contentsShow
← Computer Science
Lesson 932 of 2,87222. Dynamic ProgrammingFree lesson

Subset Sum Problem

Determine if a subset of numbers exists that sums to a target value using boolean DP table.

Subset Sum Problem

You'll learn how to use dynamic programming to check whether any subset of numbers can add up to a target value.

What is the Subset Sum Problem?

Given an array of numbers and a target sum, you need to determine if there's any subset (a selection of numbers) that adds up exactly to that target. For example, with [3, 5, 2, 8] and target 10, the answer is "yes" because 3 + 5 + 2 = 10.

This is a classic 0/1 decision problem: each number is either included or excluded from the subset.

The DP Approach

Instead of trying all possible subsets (which would be exponential), we use a boolean DP table where dp[i][j] means: "Can we form sum j using the first i numbers?"

Building the Table

  • Base case: dp[0][0] = true (we can make sum 0 with zero numbers)
  • Recurrence: For each number at position i and each target sum j:
    • If we don't include this number: dp[i][j] = dp[i-1][j]
    • If we include this number (and it doesn't exceed j): dp[i][j] = dp[i-1][j - nums[i]]
    • We take the OR of both options

Think of it like a checklist: "Can I reach this sum either without the current number, or with it (by having reached the smaller sum before)?"

The final answer is dp[n][target], where n is the array length.

This builds on the 0/1 Knapsack approach—each element is either in or out—but tracks boolean feasibility instead of maximizing value.

Key Takeaway: The Subset Sum Problem uses a 2D boolean DP table to efficiently check if any combination of numbers sums to a target, avoiding exponential brute-force enumeration.