A decision problem so simple a child can understand it, yet so hard that no polynomial-time solution is known to exist. Subset Sum is NP-complete — and yet it yields to a beautifully structured dynamic programming approach that runs in pseudo-polynomial time. In this lecture, we build up from first principles: what the problem means, why it is hard, where that hardness comes from, and how dynamic programming navigates the search space that brute force cannot.
Imagine you are packing a bag with a strict weight limit. You have a pile of items, each with a known weight, and you want to know: is there any combination of items that fills the bag to exactly the limit — not under, not over, but precisely at the limit? This is the essence of the Subset Sum problem.
Notice carefully what is being asked. The question is not "which combination is closest?" or "what is the maximum we can fit?" — it is purely binary: can it be done exactly, yes or no? This distinction is not a simplification — it is the whole point. Subset Sum is what computer scientists call a decision problem: a question with exactly two possible answers.
Decision problems are the bedrock of complexity theory. Their clean yes/no structure makes it possible to mathematically compare the difficulty of different problems against one another. When we later say that Subset Sum is "NP-complete," we mean it specifically as a decision problem. Keep this framing in mind — it will become essential in Section 6. With that intuition established, let us now state the problem precisely.
Given a finite multiset of non-negative integers S = {a₁, a₂, ..., aₙ}
and a non-negative integer target t, the Subset Sum problem asks:
Does there exist a subset S' ⊆ S such that Σaᵢ ∈ S' aᵢ = t ?
If such a subset exists, the answer is YES, and any subset with this property is called a witness or certificate for the YES answer. If no such subset exists, the answer is NO.
It is worth pausing here, because students often confuse Subset Sum with two related but genuinely harder tasks. Understanding how these differ will clarify exactly what our algorithms must accomplish.
The decision version asks: does a solution exist? Answer YES or NO.
The search version asks: if one exists, find and return the actual subset.
The search version is at least as hard as the decision version — you cannot find
a solution without first knowing one exists. For Subset Sum specifically, if you can
solve the decision problem efficiently, you can also solve the search problem by
a sequence of decision queries. In this lecture, we focus on the decision version.
The optimization version (the Knapsack problem) asks: what is the
maximum-value subset whose total weight does not exceed a given capacity?
This is strictly harder than asking a single YES/NO question. In complexity theory,
decision problems are the canonical form because the YES/NO structure maps cleanly
to the definitions of P and NP — both of which are defined in terms of decision
problems, not optimization tasks.
Notice the definition uses the word multiset rather than set.
A true set cannot contain duplicate values, but a multiset can. This matters here.
Consider S = {5, 5, 3} with target t = 10: picking both 5s
gives a sum of 10 — a valid solution. If S were a true set with no duplicates, there
would be only one 5, and this solution would be impossible.
The practical consequence is that our algorithms must treat elements by position, not by value. The element at index 0 and the element at index 1 are always distinct candidates, even if both hold the value 5. Keep this in mind when we build the DP table in Section 4 — each row corresponds to one position, not one unique value.
Before going further, let us see the definition in action across three different scenarios. These examples will also serve as test cases for both algorithms later.
Example C highlights an important asymmetry. A YES answer can always
be verified in a single pass — just sum the proposed subset and check against t.
A NO answer, however, has no short certificate in general: you cannot
exhibit a small proof that no solution exists, because any such proof would amount to
checking all possibilities. This asymmetry between easy verification and hard refutation
is the defining characteristic of the class NP — and it is why Subset Sum's
NP-completeness is a deep result, not a trivial one.
Subset Sum is not a purely theoretical construction. Its structure recurs across surprisingly diverse real-world domains, which is part of why understanding it matters beyond this course.
In each case, the difficulty is the same: the space of candidate subsets grows exponentially with the number of items. How we navigate that space — and what structure we can exploit to avoid checking everything — is the central question of this lecture.
Before moving on, confirm you can answer these questions from memory:
We have defined the problem and seen a few examples. Now, before we think about algorithms at all, let us work through a single instance completely by hand. This matters for a specific reason: before you can design an algorithm to solve a problem efficiently, you need to understand what a solution actually requires at each step. What decisions are made? In what order? What information do you need to carry from one step to the next? This section answers all three questions through a fully annotated manual trace.
Work through every step carefully. The intuition you build here — especially the observation about repeated work at the end — is the foundation for everything in Section 4.
S = {3, 1, 4, 2}, target t = 5
We have n = 4 elements. Each element is either included in our chosen subset
or it is not — an independent binary choice. With 4 such choices, the total number of
distinct subsets is 2⁴ = 16. We must be prepared to examine all of them.
Let us do so now, one by one.
To enumerate subsets systematically without repetition or omission, we use the following
encoding: each subset of an n-element array corresponds uniquely to a binary
string of length n. A 1 at position i means
"include element i"; a 0 means "exclude it."
For our 4-element array, we use 4-bit strings — integers from 0000 (binary 0,
the empty subset) to 1111 (binary 15, the full set). Counting from 0 to
2ⁿ − 1 in binary visits every subset exactly once. This correspondence is
bijective — every subset maps to exactly one integer, and every integer maps to exactly
one subset. This is the mental model behind every brute-force implementation.
Now let us walk through the complete search table. For each of the 16 subsets, we record the bitmask, the subset it represents, the sum computation, and whether the sum matches our target of 5. Read this row by row, exactly as a brute-force algorithm would process it. Note where the first YES appears, and consider what happens if no YES ever does.
| Mask | Subset S' | Sum Calculation | Sum | = t (5)? |
|---|---|---|---|---|
| 0000 | ∅ (empty set) | — | 0 | NO |
| 0001 | {2} | 2 | 2 | NO |
| 0010 | {4} | 4 | 4 | NO |
| 0011 | {4, 2} | 4 + 2 | 6 | NO |
| 0100 | {1} | 1 | 1 | NO |
| 0101 | {1, 2} | 1 + 2 | 3 | NO |
| 0110 | {1, 4} | 1 + 4 | 5 | YES ✓ |
| 0111 | {1, 4, 2} | 1 + 4 + 2 | 7 | NO |
| 1000 | {3} | 3 | 3 | NO |
| 1001 | {3, 2} | 3 + 2 | 5 | YES ✓ |
| 1010 | {3, 4} | 3 + 4 | 7 | NO |
| 1011 | {3, 4, 2} | 3 + 4 + 2 | 9 | NO |
| 1100 | {3, 1} | 3 + 1 | 4 | NO |
| 1101 | {3, 1, 2} | 3 + 1 + 2 | 6 | NO |
| 1110 | {3, 1, 4} | 3 + 1 + 4 | 8 | NO |
| 1111 | {3, 1, 4, 2} | 3 + 1 + 4 + 2 | 10 | NO |
The exhaustive search reveals two valid subsets:
{1, 4} (mask 0110, sum = 5) and
{3, 2} (mask 1001, sum = 5). The answer is YES.
A brute-force algorithm stops at the first YES it finds — here, at mask 6 (binary 0110),
after checking only 7 of the 16 subsets. But for a NO instance, there is no early exit:
every single one of the 2ⁿ subsets must be checked before we can confidently report NO.
That worst case defines the algorithm's complexity.
Now step back and notice something important about how this table was generated. The brute-force algorithm has no intelligence about the problem's structure — it does not reason about which subsets are "promising." It simply counts from 0 to 15 and mechanically evaluates each bitmask as an isolated candidate.
This is the defining character of brute force: it is complete
(it will always find a solution if one exists) and sound (it will never
report YES incorrectly), but it is profoundly wasteful. It treats the
search space as a flat list of unrelated candidates and evaluates each one from scratch.
It does not remember that subset {1} sums to 1, so when it evaluates
{1, 4}, it recomputes the contribution of element 1 from the beginning.
This repeated recomputation of partial sums is precisely the redundancy that dynamic
programming will eliminate.
Consider changing the target slightly: set t = 9 with the same
S = {3, 1, 4, 2}. Scanning the table above, no subset sums to 9
(the closest values are 8 and 10). To prove this is a NO instance, the algorithm
must check all 16 subsets — there is no way to conclude "9 is unreachable"
until every possibility has been ruled out.
This is not a weakness of our particular implementation. It reflects something fundamental: without additional structure, you cannot prove the absence of a solution without ruling out every candidate. This is why NO instances drive the worst-case complexity, and it is a key reason why Subset Sum is classified as NP-hard — the hardest YES/NO questions are always the ones that turn out to be NO.
Before continuing, make sure you can explain the following from the trace above:
0110 translate into the subset {1, 4}?We have just seen that brute force correctly solves our 4-element example by checking all 16 subsets. Now comes the critical question: what happens when we scale up? Not to a thousand elements, but even modestly — to 40, 50, or 60?
The answer is unsettling. Subset Sum does not just become "harder" for larger inputs in the ordinary sense — it becomes qualitatively impossible in a way that no engineering improvement can overcome. Understanding exactly why is one of the deepest insights in this course.
To understand the exponential growth, we need to trace it back to its origin in the problem's structure itself — not in our algorithm, but in the problem.
For each element aᵢ in S, we face exactly one binary decision:
include it or exclude it. These decisions are completely independent — the choice
we make for a₁ places no constraint on what we choose for a₂,
a₃, and so on. Independent binary choices are multiplicative:
two elements give 2 × 2 = 4 combinations; three give
2 × 2 × 2 = 8; four give 16. The general formula is:
A particularly useful way to picture this growth is as a binary decision tree.
At the root, we make a choice about element a₁: the left branch means
"exclude," the right means "include." Each of those two nodes then branches again
for a₂. At depth k, we have 2ᵏ nodes —
one for each partial decision sequence so far.
The leaves of this tree, at depth n, each represent one fully determined
subset. A brute-force algorithm is equivalent to visiting every leaf — all 2ⁿ
of them — in sequence. There is no pruning and no shortcut in the worst case.
The size of this tree is the fundamental lower bound on what brute force must do.
Here is why adding one element to S always doubles the work,
without any exception. Suppose we have already enumerated all 2ⁿ subsets
of an n-element set S. We now add a new element aₙ₊₁.
Every subset of the extended set S ∪ {aₙ₊₁} is one of exactly two kinds:
Kind A — excludes aₙ₊₁: These are exactly the same as all subsets of
the original S. There are 2ⁿ of them, unchanged.
Kind B — includes aₙ₊₁: Each is formed by taking any subset of the
original S and appending aₙ₊₁. Since there are 2ⁿ
subsets of S, there are exactly 2ⁿ Kind B subsets as well.
Total: 2ⁿ + 2ⁿ = 2 × 2ⁿ = 2ⁿ⁺¹. Every new element doubles the count.
This is not an approximation — it is exact, and it holds regardless of the values in S.
A natural response to seeing these numbers is to ask: could faster hardware help? Could a supercomputer, a quantum computer, or a billion processors in parallel make brute force feasible for larger inputs? The answer, surprisingly, is no — and the reason reveals something deep about the difference between exponential and polynomial growth.
| n (elements) | 2ⁿ (subsets) | Time @ 10⁹ ops/sec | Verdict |
|---|---|---|---|
| 10 | 1,024 | < 1 microsecond | Trivial |
| 20 | 1,048,576 | ~1 millisecond | Easy |
| 30 | 1,073,741,824 | ~1 second | Borderline |
| 40 | 1,099,511,627,776 | ~18 minutes | Slow |
| 50 | 1.13 × 10¹⁵ | ~13 days | Infeasible |
| 60 | 1.15 × 10¹⁸ | ~36 years | Infeasible |
| 100 | 1.27 × 10³⁰ | ≫ age of the universe | Impossible |
Suppose we build a computer one million times faster than today's —
10¹⁵ operations per second. How does this change the table?
It shifts every entry up by six rows: n = 60 now takes about 30 seconds
instead of 36 years. That seems like progress.
But now consider n = 80 — just 20 elements further. This is 2²⁰
times harder than n = 60, which means it takes
30 seconds × 1,048,576 ≈ 1 year on our hypothetical machine.
We spent a factor of one million in hardware to buy 20 extra elements of headroom.
This is the iron law of exponential growth: a constant factor speedup
buys only a constant number of extra elements —
specifically, log₂(speedup factor) more. Doubling your processor count
buys exactly one extra element. A billion processors buy 30 more. No realistic hardware
improvement can bring large instances into reach.
Let us be precise about where the exponential enters the brute-force algorithm, because students sometimes think optimized implementations can avoid it. Here is the complete pseudocode:
Notice: the outer loop runs exactly 2ⁿ times. Not approximately, not
at most — exactly. Each iteration represents one distinct subset, and we must visit
every subset. No matter how fast we make the inner sum computation, the outer loop
remains. The exponential is not in the cost per subset — it is in the
number of subsets, and that number is determined by the problem's structure,
not by our implementation choices.
There is, however, something that brute force completely ignores — a structural observation that will form the entire foundation of the dynamic programming approach. Look carefully at these four subset evaluations from our example:
Every subset that contains element 1 recomputes its contribution from scratch.
The fact that {1} sums to 1 is discovered on row 4, discarded, then
rediscovered on row 6, discarded, and rediscovered again on row 5. More generally,
a prefix of length k appears in 2^(n−k) different subsets,
and its sum is recomputed every single time.
This is an enormous amount of wasted effort. And it suggests a clear solution: if we stored the result of computing a prefix's reachable sums, we could reuse it every time that prefix appears, rather than recomputing it. Storing intermediate results to avoid redundant recomputation is precisely the idea behind dynamic programming — and it is what we develop rigorously in the next section.
Brute force is not logically wrong — it is computationally wasteful.
It solves the same sub-problems repeatedly and discards their answers immediately.
Dynamic programming solves each sub-problem exactly once and remembers
the result in a table. The price paid is memory: we need a table large enough
to store all intermediate results. The reward is a dramatic reduction in time —
from O(2ⁿ) down to O(n × t).
Whether that reward is always worth it is a subtler question — and it depends
on the value of t. That subtlety is the very reason Subset Sum remains
NP-complete despite having a pseudo-polynomial solution.
Before continuing, make sure you can answer the following:
We have established three things: brute force is correct, it is exponentially slow, and its slowness comes from redundantly recomputing the same partial sums over and over. Now we ask the constructive question: what is the minimum information we need to remember in order to never recompute anything twice?
The answer to that question is dynamic programming. But before we write any recurrence or fill any table, we need to build the intuition carefully — because the formal machinery will feel completely natural once you see why it is necessary.
Recall the key observation from Section 3: brute force treats every subset as an
independent problem, but subsets are not independent. They share prefixes. The sum
of {1, 4} is just the sum of {1} plus 4. The sum of
{3, 1, 4} is just the sum of {1, 4} plus 3. Every subset
is a smaller subset with one element added.
This gives us a way to decompose the problem into a structured family of
smaller questions. Instead of asking "which of the 2ⁿ subsets sums to
t?", we ask a more manageable question:
"what are all the sums achievable using exactly the first i elements?"
If we answer this for every value of i from 0 to n,
we have answered the original question as a special case — when i = n.
1. Optimal Substructure: The solution to dp[i][s] depends only on solutions to strictly smaller sub-problems — dp[i−1][s] and dp[i−1][s−aᵢ]. No sub-problem needs to "look ahead" or revisit earlier rows. This means optimal solutions compose: if we know the best answer for the first i−1 elements, we can extend it optimally by one element at a time.
2. Overlapping Sub-problems: Many different paths through the decision tree lead to the same (i, s) state. For example, whether we reach "can first 3 elements sum to 4?" via {1,3} or {4} or {1,2,1}, the answer is the same boolean stored in dp[3][4]. Brute force recomputes this every time; DP stores it once. This shared structure is what gives DP its advantage — without it, memoization would save nothing.
The key observation is this: the set of sums achievable using the first
i elements can be computed entirely from the set of sums
achievable using the first i−1 elements. We do not need to look further
back than one step. This is called the optimal substructure property,
and it is what makes dynamic programming applicable.
Specifically: when we introduce element aᵢ, every previously reachable
sum s generates one new potentially reachable sum — s + aᵢ.
All the old sums remain reachable too (by excluding aᵢ). So the new
reachable set is simply: the old reachable set, plus a copy of the old
reachable set shifted upward by aᵢ.
Before writing any recurrence, we need to define precisely what we are computing. In dynamic programming, this is called the state — the complete description of a sub-problem. A well-chosen state is the most important design decision in any DP solution.
For Subset Sum, the natural state involves two variables: how far into the array we are, and what target sum we are asking about.
The sub-problem for state (i, s) is: "Using only the first
i elements of the array, can we form a subset that sums to exactly
s?" We store the answer in dp[i][s], a single boolean value.
dp[i][s] = true if some subset of {a₁, …, aᵢ}
sums to exactly s.
dp[i][s] = false if no such subset exists.
The final answer to the original problem is dp[n][t]: using all n
elements, can we achieve the target? Every other cell is a helper sub-problem
used to compute this final answer.
Notice that we have (n+1) × (t+1) states in total. For our example with
n = 4, t = 5, that is only 5 × 6 = 30 states — compared to
2⁴ = 16 subsets for brute force. For larger inputs, when t
is moderate, the savings are enormous.
Now we derive the rule for computing dp[i][s] from the cells we have
already filled. The key question is: given that we want to know whether sum s
is achievable using the first i elements, what exactly do we need to know
from the previous row?
Consider the role of element aᵢ. In any subset that achieves sum s,
element aᵢ is either included or it is not. There is no third option.
These two cases are exhaustive and mutually exclusive — which is why they produce a
clean two-case recurrence.
Case 1 — Exclude aᵢ: The entire sum s must come from
the first i−1 elements alone. Whether this is possible is exactly what
dp[i−1][s] records. So if dp[i−1][s] is true, then
dp[i][s] is also true — the new element changes nothing.
Case 2 — Include aᵢ: Element aᵢ contributes its value,
so the remaining elements (from the first i−1) must cover
s − aᵢ. This only makes sense when s ≥ aᵢ, since our
elements are non-negative and cannot produce negative contributions. If the
non-negative integer assumption were violated — that is, if any element
aᵢ could be negative — then s − aᵢ could exceed
s, accessing a column index beyond the table bounds and making the
recurrence undefined. The entire DP formulation depends on this assumption holding.
Whether
s − aᵢ is reachable is exactly what dp[i−1][s − aᵢ]
records.
dp[i][s] is true if and only if at least one of these two cases is true.
This is the logical OR in the recurrence below.
The base cases are not arbitrary initializations — they encode a precise fact about
the problem's starting state. With zero elements available, the only subset we can
form is the empty subset ∅, which sums to 0 by definition.
dp[0][0] = true — the empty subset achieves sum 0. This is always true, trivially.dp[0][s] = false for all s > 0 — with no elements, no positive sum is reachable. Equally trivial.These two base cases seed the entire table. The recurrence then propagates truths forward, row by row — each new row extending the possibilities opened by the previous one. Think of it as watching reachable sums accumulate as we consider more and more elements.
Now let us fill the DP table for S = {3, 1, 4, 2}, t = 5, exactly
as the algorithm would, and reason through every non-trivial cell explicitly.
Each row i represents the state after considering the first i
elements. Cells marked T are true; blank cells are false.
For each cell dp[i][s], ask: can the first i elements
of {3, 1, 4, 2} form a subset summing to exactly s?
Apply the recurrence: look up dp[i−1][s] (exclude element i)
and, if s ≥ aᵢ, also look up dp[i−1][s−aᵢ] (include it).
If either lookup is true, the current cell is true.
| Row / Element | s = 0 | s = 1 | s = 2 | s = 3 | s = 4 | s = 5 |
|---|---|---|---|---|---|---|
| i=0 (no elements) | T | F | F | F | F | F |
| i=1 (consider a₁=3) | T | F | F | T | F | F |
| i=2 (consider a₂=1) | T | T | F | T | T | F |
| i=3 (consider a₃=4) | T | T | F | T | T | T ✓ |
| i=4 (consider a₄=2) | T | T | T | T | T | T ✓ |
Now let us trace through the key cells that are not immediately obvious. Follow each step closely — this is the exact reasoning the algorithm performs.
dp[1][0]: Exclude 3 → dp[0][0] = true. → T. (Empty subset still sums to 0.)
dp[1][1] and dp[1][2]: Exclude 3 → dp[0][1] = dp[0][2] = false. Include 3 → s < 3, impossible. → F.
dp[1][3]: Exclude 3 → dp[0][3] = false. Include 3 → s = 3 ≥ 3, check dp[0][3−3] = dp[0][0] = true. → T. Witness: {3}.
dp[1][4] and dp[1][5]: Include 3 → dp[0][1] = dp[0][2] = false. Exclude 3 → same. → F.
Now we consider element 1 on top of what row 1 already established.
dp[2][1]: Exclude 1 → dp[1][1] = false. Include 1 → s = 1 ≥ 1, check dp[1][0] = true. → T. Witness: {1}.
dp[2][4]: Exclude 1 → dp[1][4] = false. Include 1 → check dp[1][3] = true. → T. Witness: {3, 1}.
dp[2][5]: Exclude 1 → dp[1][5] = false. Include 1 → check dp[1][4] = false. → F.
Notice that sum 5 is still not reachable using only {3, 1} — we need more elements.
dp[3][5]: Exclude 4 → dp[2][5] = false. Include 4 → 5 ≥ 4, check dp[2][5−4] = dp[2][1] = true. → T!
This is the critical step. dp[2][1] = true tells us that sum 1 was reachable with the first two elements — specifically, using {1}. Adding element 4 extends that sum to 1 + 4 = 5. The witness is {1, 4}. Notice that the algorithm never explicitly formed this subset — it simply tracked reachable sums and observed that the gap from 1 to 5 was exactly 4. This is the elegance of the DP approach.
dp[4][2]: Include 2 → check dp[3][0] = true. → T. Witness: {2}.
dp[4][5]: Exclude 2 → dp[3][5] = true (already established). → T. Confirmed.
Additionally, via inclusion: check dp[3][3] = true (reachable via {3}), and 3 + 2 = 5.
This reveals the second witness {3, 2} — the same one brute force
found at mask 1001. Both witnesses are encoded in the table simultaneously,
even though the table stores only boolean values and never lists them explicitly.
At this point you may be thinking: the DP runs in O(n × t) time, which
looks like a polynomial. Two variables multiplied together — that sounds tractable.
Why, then, is Subset Sum still considered NP-complete?
The answer lies in a subtle but fundamental distinction in how we measure input size. In complexity theory, the "size" of an input is the number of bits required to write it down — not the magnitude of the numbers involved. This distinction is critical.
Consider the target value t. To write t = 1,000,000 in binary,
you need only about log₂(1,000,000) ≈ 20 bits. Let us call this
L = ⌈log₂(t)⌉ — the bit-length of t. Then:
Let S = {1, 2, 4, 8, …, 2^(n−1)} — powers of 2 — and let
t = 2ⁿ − 1 (the sum of all elements).
The input itself is compact: n numbers, each needing about n bits,
so the total input size is roughly O(n²) bits — small and well-behaved.
But the DP table has n × (2ⁿ − 1) ≈ n × 2ⁿ cells.
For n = 60: the input fits comfortably in memory (about 3,600 bits).
But the DP table has 60 × 2⁶⁰ ≈ 6.9 × 10¹⁹ cells — far more than any
computer could store or process. The DP offers no advantage over brute force on this
input. This is precisely why O(n × t) is called pseudo-polynomial:
it is polynomial in the value of t, but exponential in the
bit-length of t, which is the true measure of input size.
Both algorithms — brute force and DP — are thus exponential in the worst case.
They simply fail on different types of inputs: brute force when n is large,
and DP when t is large. The problem remains NP-complete because NP-completeness
is a statement about worst-case behavior over all possible inputs,
and we cannot guarantee that t will be small. In practice, when t
is moderate (say, at most a few million), the DP is extremely efficient — and that is
why it is the algorithm of choice for real applications.
Enumerate all 2ⁿ subsets via bitmask. For each, compute its sum and compare to t. Stop on first match; report NO after exhaustion.
Fill a boolean table dp[i][s] bottom-up. Each cell answers: can the first i elements achieve sum s? Answer in dp[n][t].
The DP algorithm is exact and efficient only within a specific
tractable subclass: instances where t
is polynomially bounded in n — that is,
t = O(nᵏ) for some fixed constant k.
Within this subclass, O(n·t) = O(nᵏ⁺¹), which is a
genuine polynomial and the DP runs efficiently in polynomial time.
Outside this subclass — when t grows
exponentially in n — the DP fails as a practical
algorithm. The precise boundary is t = O(2ⁿ): once
t reaches this scale, the DP table has
O(n · 2ⁿ) cells, exponential in the input size.
Tight instance where DP fails outside the tractable subclass:
S = {1, 2, 4, 8, …, 2ⁿ⁻¹}, t = 2ⁿ − 1.
Here t is exponential in n. The DP table
has n × (2ⁿ−1) cells. For n = 60:
approximately 6.9 × 10¹⁹ cells — computationally
infeasible despite the DP being theoretically correct. This is the
exact instance that sits outside the tractable subclass boundary and
demonstrates where the algorithm breaks down.
Before moving to the interactive tool, confirm you can explain the following:
dp[i][s] represent, in plain English?dp[3][5] become true when dp[2][5] was still false?Press Build Steps to initialize the algorithm, then use Step or Play to animate the execution.
dp[i][s] value means.
Click "Build Steps" to place a live marker at your current n value.
Everything we have done so far — brute force, dynamic programming, the DP table, the interactive tool — has been about solving Subset Sum.
This section is about something deeper: classifying it. We want to understand exactly how hard Subset Sum is in a formal, mathematical sense, and prove that hardness rigorously.
The conclusion is that Subset Sum is NP-complete — one of the most important classifications in all of theoretical computer science. This means two things simultaneously, and both must be proven independently. Neither implies the other.
A problem X is NP-complete if and only if: (1) X is in NP — any claimed solution can be verified in polynomial time — and (2) X is NP-hard — every problem in NP can be reduced to X in polynomial time.
The consequence: if any NP-complete problem has a polynomial-time algorithm, then all NP problems do — resolving the P vs. NP question (a $1,000,000 Millennium Prize problem open since 1971). No such algorithm is known, and most complexity theorists believe none exists.
Before entering the proof, it helps to see exactly where these four classes sit relative to each other. They are routinely conflated in textbooks and casual usage — particularly NP-Hard and NP-Complete, which are related but meaningfully distinct. The diagram below shows their precise containment relationships; the definitions that follow ground each term formally.
Figure: Containment relationships under the standard assumption P ≠ NP (unproven but widely believed). NP-Hard problems are at least as hard as every NP problem; those also in NP form the NP-Complete class. The Halting Problem is NP-Hard but undecidable — it is not even in NP.
Problems solvable by a deterministic algorithm in O(nk) time for some constant k. These are the tractable problems — fast enough to scale to large real-world inputs.
Problems whose solutions can be verified in polynomial time. Every P problem is in NP (solving implies verifying), but NP is potentially much larger. Whether P = NP is the central open question of computer science.
Problems to which every NP problem can be reduced in polynomial time. At least as hard as the hardest problems in NP, but not required to be in NP themselves — some NP-Hard problems are undecidable.
The intersection of NP and NP-Hard: problems that are both verifiable in polynomial time and at least as hard as every other NP problem. If any one is solvable in polynomial time, every NP problem is.
Without this framework, declaring a problem “hard” is an informal, unprovable claim. These classes make hardness rigorous. Proving Subset Sum is NP-complete achieves two things simultaneously: it provides a mathematical proof that no polynomial-time algorithm exists for it unless P = NP, and it places Subset Sum in a vast equivalence class — one where solving any single member efficiently solves all of them. Hundreds of fundamental problems across scheduling, cryptography, and combinatorics share this fate.
This is precisely why the proof that follows requires two independent parts: NP membership and NP-hardness. NP-completeness is their conjunction — neither condition alone is sufficient.
Being in NP does not mean a problem is hard to solve. It means a problem has a specific structural property: if someone hands you a proposed solution (called a certificate), you can check whether that solution is correct in polynomial time. This is the formal definition, and it is surprisingly easy to satisfy for Subset Sum.
For any YES instance of Subset Sum, the certificate is simply a
list of indices identifying which elements of S make up the claimed
solution subset S' ⊆ S. For example, if
S = {3, 1, 4, 2} and t = 5, a valid certificate
might be [1, 2] (indices of elements 1 and 4).
The certificate has size at most n — one index per element —
which is polynomial in the input size. It is a compact, efficiently representable
proof that a solution exists.
Given a certificate (a list of indices), the verifier performs two checks:
S = {a₁, …, aₙ}tI ⊆ {0,…,n−1}I is valid (0 ≤ i < n)sum = Σ S[i] for i ∈ Isum == tO(n)O(n) — linearNotice that verification is dramatically easier than solving: to verify, we need one specific subset handed to us. To solve, we must search through all 2ⁿ candidates. This asymmetry is the heart of the P vs. NP question.
Subset Sum is in NP because: given a proposed subset S',
we can verify in O(n) time whether Σ S' = t. The certificate
has polynomial size (at most n elements). Therefore
Subset Sum ∈ NP. ∎
To prove Subset Sum is NP-hard, we must show that every problem in NP is at least as hard as every problem in NP.
We cannot enumerate all NP problems, so we use a transitivity argument: we pick one known NP-complete problem and reduce it to Subset Sum. If that reduction works, then by transitivity, all NP problems reduce to Subset Sum.
We choose 3-SAT as our starting point, because it is the canonical
NP-complete problem (Cook's theorem, 1971). A 3-SAT instance consists of n
boolean variables x₁, …, xₙ and m clauses, each a disjunction
of exactly 3 literals.
We must construct a Subset Sum instance that is satisfiable if and only if the 3-SAT formula is satisfiable.
The key idea is to encode both the variable assignments and the clause satisfaction conditions using the digits of carefully constructed integers. We work in base 10 with enough digits that no carrying ever occurs between digit positions.
The construction creates 2n + 2m numbers, each written with n + m decimal digits. The digits are arranged in two groups of columns:
Role: enforce a consistent truth assignment for each variable.
There is one digit position for each of the n variables.
For variable xᵢ, two numbers are created:
xᵢ: has a 1 in digit position i and also 1s in clause positions for clauses where xᵢ appears positively.xᵢ: has a 1 in digit position i and also 1s in clause positions for clauses where ¬xᵢ appears.
Because both vᵢ and v'ᵢ have a 1 in digit position i,
and the target requires exactly 1 at that position,
exactly one of the two must be selected
— enforcing a consistent truth assignment.
If both were chosen, the digit sum at that position would be 2, which exceeds the target value of 1. Therefore, such a subset is automatically invalid, enforcing that exactly one must be selected.
Role: ensure every clause is satisfied by at least one literal.
There is one digit position for each of the m clauses.
For clause Cⱼ, two slack numbers are created:
j.j.A clause is satisfied by 1, 2, or 3 of its literals. The variable rows contribute 1, 2, or 3 to the clause digit. The target requires exactly 4 at each clause digit.
The slack numbers allow any satisfied clause (1–3 literals true) to be padded up to 4, but an unsatisfied clause (0 literals true) can never reach 4 regardless of which slacks are chosen.
Let us make this concrete. Consider the formula:
(x₁ ∨ x₂ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₂) — simplified to illustrate the
structure.
With n = 2 variables and m = 2 clauses, we create
2×2 + 2×2 = 8 numbers, each with 2 + 2 = 4 digits.
The digit columns are: x₁ | x₂ | C₁ | C₂.
| Number | Variable digits | Clause digits | Represents | ||
|---|---|---|---|---|---|
| x₁ | x₂ | C₁ | C₂ | ||
| v₁ (x₁ = TRUE) | 1 | 0 | 1 | 0 | x₁=T satisfies C₁ |
| v'₁ (x₁ = FALSE) | 1 | 0 | 0 | 1 | ¬x₁=T satisfies C₂ |
| v₂ (x₂ = TRUE) | 0 | 1 | 1 | 1 | x₂=T satisfies C₁, C₂ |
| v'₂ (x₂ = FALSE) | 0 | 1 | 1 | 0 | ¬x₂=T satisfies C₁ |
| s₁ (slack for C₁) | 0 | 0 | 1 | 0 | Pads C₁ digit by 1 |
| s'₁ (slack for C₁) | 0 | 0 | 2 | 0 | Pads C₁ digit by 2 |
| s₂ (slack for C₂) | 0 | 0 | 0 | 1 | Pads C₂ digit by 1 |
| s'₂ (slack for C₂) | 0 | 0 | 0 | 2 | Pads C₂ digit by 2 |
| Target T | 1 | 1 | 4 | 4 |
1 per var position (exactly one of vᵢ/v'ᵢ chosen); 4 per clause position (at least one literal satisfied + slack fills to 4) |
The construction only works if digits at different positions never interfere through carrying. At any clause digit position, the maximum possible sum is:
3 (variable rows) + 1 (sj) + 2 (s'j) = 6 → 6 < 10 ∴ no carry ✓
At any variable digit position, the maximum contribution is 2 (both vᵢ
and v'ᵢ selected — which the construction prevents, but must be verified).
At variable digit positions, at most two numbers contribute (vi and v'i,
each with digit value 1), giving a maximum sum of 2 < 10 — also no carry. ✓
In practice, the base is chosen large enough to prevent carries at every position. Proving this rigorously is a non-trivial part of the formal proof — without it, the bijection between digit sums and satisfiability breaks down.
A reduction is only valid if it preserves the YES/NO answer in both directions.
We must show that the 3-SAT formula is satisfiable if and only if the
constructed Subset Sum instance has a solution summing to T.
This requires proving two separate implications.
Assume the 3-SAT formula has a satisfying assignment. We must construct a valid subset.
xᵢ: if the assignment sets xᵢ = TRUE,
include vᵢ in the subset. Otherwise include v'ᵢ.
This ensures exactly one of each pair is selected → variable digit positions
sum to exactly 1 each. ✓
Cⱼ: the satisfying assignment makes at least one
literal true, so the variable rows contribute 1, 2, or 3 to clause digit j.
The target requires 4. The shortfall is 3, 2, or 1 respectively.
Include the appropriate slack(s) to top up to exactly 4. ✓
T digit by digit (no carries by
construction). Therefore the Subset Sum instance answers YES. ✓
Digit-by-digit verification for the 2×2 worked example:
Suppose x₁=TRUE, x₂=TRUE (both true). Then we include v₁ (1,0,1,0) and v₂ (0,1,1,1).
Both clauses are satisfied by 2 literals each, so the clause digit for C₁ gets 1+1=2 from
variable rows, needing 2 more to reach 4 — include s'₁ (0,0,2,0). Clause C₂ gets 0+1=1,
needing exactly 3 more — include both s₂ and s'₂.
Digit sum: variable x₁: 1+0=1 ✓ | variable x₂:
0+1=1 ✓ | clause C₁:
1+1+2=4 ✓ | clause C₂:
0+1+1+2=4 ✓.
The chosen subset {v₁, v₂, s'₁, s₂, s'₂} sums digit-by-digit to T = (1,1,4,4). No carry
occurs since no digit exceeds 4 < 10. ∎
Assume some subset sums to exactly T. We must extract a satisfying assignment.
i are vᵢ (contributes 1) and v'ᵢ
(contributes 1). So exactly one of the two is in the subset.
If vᵢ is chosen, set xᵢ = TRUE; if v'ᵢ,
set xᵢ = FALSE. ✓
This works because slack numbers (sj and s'j) contribute exactly 0
to every variable digit position — they only affect their own clause column. Therefore no
combination of slack variables can ever bring a variable digit from 0 to 1; only
vᵢ or v'ᵢ can do that. This guarantees the assignment
extraction is unambiguous.
The construction runs in O((n+m)²) time — polynomial in the formula size. Crucially, the reduction is both complete (every YES instance of 3-SAT maps to a YES Subset Sum instance) and sound (every YES Subset Sum instance maps back to a satisfying assignment) — proven in Part 3 above. The forward and backward directions both hold. Therefore 3-SAT ≤p Subset Sum, which means Subset Sum is NP-hard. Since 3-SAT is NP-complete and we have shown 3-SAT ≤p Subset Sum, it follows by transitivity that every problem in NP reduces to Subset Sum. ∎
Combining Steps 1 and 2: Subset Sum ∈ NP and Subset Sum is NP-hard. Therefore Subset Sum is NP-complete. ∎
This is one of the most commonly misunderstood points in the entire subject, and it is
exactly the kind of question an instructor will ask during the Q&A. The dynamic programming
solution runs in O(n × t) time. If Subset Sum is NP-complete, how can we
have an efficient algorithm for it? The answer lies in a distinction that is subtle but
absolutely fundamental.
"The DP algorithm runs in O(n × t) time. That's polynomial. So Subset Sum must be in P. But you just said it's NP-complete. That's a contradiction." — This reasoning is wrong, and the error is in the phrase "that's polynomial." Let us see exactly why.
In complexity theory, polynomial time means polynomial in the number of bits needed to write down the input — the size of the input, not the magnitude of its values. This distinction is crucial.
| Concept | Example | Bit-length | DP table size | Is this polynomial time? |
|---|---|---|---|---|
| Small t | t = 1000 | ~10 bits | n × 1,000 cells | Only if t is a fixed constant — then O(n·t) = O(n). But this is not a general guarantee. For arbitrary t, DP is always pseudo-polynomial, regardless of how small t happens to be in one instance. |
| Moderate t | t = 1,000,000 | ~20 bits | n × 1,000,000 cells | Manageable in practice — but O(n × 2²⁰) in formal terms |
| Large t = 2ⁿ | n = 60, t = 2⁶⁰ | 60 bits | 60 × 2⁶⁰ ≈ 6.9 × 10¹⁹ cells | No — exponential in the bit-length of t (which is n here) |
| Adversarial input ★ | S = {1, 2, 4, …, 2^(n−1)} | O(n²) bits total | n × (2ⁿ−1) cells | No — DP is no better than brute force on this instance |
Let L = ⌈log₂(t)⌉ be the number of bits needed to write t.
Then t = O(2^L). The DP table has n × t = n × O(2^L) cells —
which is exponential in L, the contribution of t
to the total input size. The DP algorithm is only "polynomial" if you measure complexity
using the value of t rather than its bit-length. That non-standard
measure is called pseudo-polynomial time.
Because Subset Sum has a pseudo-polynomial algorithm, it is classified as
weakly NP-complete — it is only hard when the numbers in the instance
are exponentially large. If we add a constraint that all numbers are bounded by a
polynomial in n (i.e., t ≤ nᵏ for some constant k),
the DP runs in genuinely polynomial time and the problem becomes easy.
In contrast, strongly NP-complete problems (like 3-SAT or Graph Coloring) remain hard even when all numbers in the input are small. They have no pseudo-polynomial algorithm unless P = NP. Subset Sum's weakness is exactly what makes it interesting at the boundary between hard and easy.
t
, but adversarial inputs with large t
expose its exponential worst case — consistent with NP-completeness.
Before the Q&A, confirm you can answer these questions clearly and precisely:
These resources and notes are provided for deeper engagement with the material. They go beyond what is strictly required for the project, but will strengthen your understanding during the Q&A session.
i depends only on row i−1. Using a single 1D boolean array and iterating s from t down to 0 avoids overwriting needed values.