Subset Sum Problem — Definition, Formula & Examples

The Subset Sum Problem asks: given a set of integers and a target value, does any subset of those integers add up exactly to the target? It is one of the most well-known problems in computer science for illustrating NP-completeness.

Given a finite set $S = \{a_1, a_2, \ldots, a_n\} \subset \mathbb{Z}$ and a target integer $T$ , the Subset Sum Problem is the decision problem of determining whether there exists a subset $S' \subseteq S$ such that $\sum_{a_i \in S'} a_i = T$ . This problem is NP-complete, meaning no known polynomial-time algorithm solves all instances, yet any proposed solution can be verified in polynomial time.

How It Works

A brute-force approach checks every possible subset of the given set, testing whether its elements sum to the target. Since a set of

n

elements has

2^n

subsets, this runs in exponential time. A dynamic programming approach improves practical performance: build a table where entry

(i, j)

records whether a subset of the first

i

elements can sum to

j

. This runs in

O(nT)

time, which is pseudo-polynomial because it depends on the numeric value of

T

, not just the input size. The problem's NP-completeness means that no algorithm is known to solve all instances in time polynomial in the length of the input.

Worked Example

Problem: Given the set

S = \{3, 7, 1, 8, 4\}

and target

T = 11

, determine whether any subset sums to 11.

Step 1: Try subsets systematically. Check

\{3, 8\}

3 + 8 = 11

Step 2: Since

3 + 8 = 11 = T

, a valid subset exists. You could also verify that

\{7, 4\} = 11

is another solution:

7 + 4 = 11

Answer: Yes, a subset summing to 11 exists — for example,

\{3, 8\}

Why It Matters

The Subset Sum Problem is a gateway to understanding NP-completeness in courses on algorithms and complexity theory. It appears directly in cryptography (some public-key schemes rely on its hardness) and in resource allocation tasks where you must decide if a budget can be met exactly. Mastering it prepares you for harder combinatorial problems like the knapsack problem and integer linear programming.

Common Mistakes

Mistake: Assuming the dynamic programming solution runs in polynomial time and therefore the problem is not truly hard.

Correction: The DP solution runs in

O(nT)

time, which is pseudo-polynomial — it is polynomial in

T

's value, not in the number of bits needed to represent

T

. For large target values, this is still exponential in input size.