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
iand each target sumj:- 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
- If we don't include this number:
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.