A problem that asks whether a subset of a given set of numbers sums up to a specific target value.

Subset Sum vs Knapsack?

Subset Sum is a variation of the 0/1 Knapsack problem where weights and values are the same, and we seek an exact target instead of a maximum.

Negative numbers in Subset Sum?

The standard DP approach works for positive integers. For negative numbers, the problem becomes significantly more complex related to the partition problem.

Subset Sum

Determine if there exists a subset of the given set of non-negative integers whose sum is equal to a specific target value.

Ready

Target Sum

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine you have a set of coins and you want to know if you can pay an exact amount. For each coin, you have two choices: include it in your payment or exclude it. If you exclude it, you still need to make the full amount with the remaining coins. If you include it, you need to make (Target - CoinValue) with the remaining coins.

Concept

Boolean Dynamic Programming:

We define `dp[i][j]` as a boolean value: Is it possible to create a sum of `j` using a subset of the first `i` items?

Recurrence Relation:

Exclude item i: Possible if `dp[i-1][j]` is true.
Include item i (if nums[i] <= j): Possible if `dp[i-1][j - nums[i]]` is true.

Result: `dp[i][j] = dp[i-1][j] OR dp[i-1][j - nums[i]]`

How it Works

Tabulation Algorithm:

Initialize a boolean table `dp` of size (n+1) \times (Target+1).
Base Case: `dp[i][0] = true` for all i (sum 0 is always possible with empty set).
Iterate through items i from 1 to n.
Iterate through target sum j from 1 to Target.
Apply the recurrence relation.
The result is in `dp[n][Target]`.

Step-by-Step Breakdown

Visualizing the boolean table:

True (T): Sum is reachable.
False (F): Sum is not reachable.
Propagation: 'True' values propagate down (exclusion) and diagonally right (inclusion).

When to Use

Applications:

Decision problems involving sums.
Load balancing (splitting tasks into two equal time sets).
Cryptography (related to Knapsack cryptosystems).

When NOT to Use

Large Target: If Target is huge, O(N*Target) is too slow.
Floating Point Numbers: DP works best with integers/discrete steps.

How to Identify

"Does a subset sum to K?", "Can we partition into two equal sums?" (Partition Equal Subset Sum).

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep