Faangprep Logo
Log inStart free
Browse curriculum

Subset Sum

The Subset Sum problem asks whether some subset of a set of non-negative integers adds up exactly to a target value.

READY

0

1

2

3

4

5

Ø

T
F
F
F
F
F

2

T
-
-
-
-
-

3

T
-
-
-
-
-

5

T
-
-
-
-
-

 

Initialize DP table. Base case: Sum 0 is always possible (True).

Next

Checking sum 1 with item 2

Target Sum

5

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:

  1. Initialize a boolean table dp of size (n+1) × (Target+1).
  2. Base Case: dp[i][0] = true for all i (sum 0 is always possible with empty set).
  3. Iterate through items i from 1 to n.
  4. Iterate through target sum j from 1 to Target.
  5. Apply the recurrence relation.
  6. 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).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

0/1 Knapsack

Next

Longest Common Subsequence

Frequently Asked Questions

What is Subset Sum?

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.