Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Decide whether some subset of the array sums to exactly T. It's the feasibility flavor of 0/1 knapsack: dp[s] is true if some subset hits sum s. The recurrence is dp[s] = dp[s] OR dp[s - num] for each number, sweeping s DESCENDING so each number is used at most once. Anchor dp[0] = true (the empty subset). O(n·T) time, O(T) space — or fold the whole row into one big integer and use bitset shifts.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize a feasibility question as boolean 0/1 knapsack, get the descending 1-D sweep right (each item once), and ideally know the bitset speedup.
Where candidates slip
Sweeping the sum ascending (which reuses numbers and answers a different problem), or forgetting dp[0] = true so no sum is ever reachable.
How to stand out
Name it as 0/1 knapsack feasibility, derive dp[s] |= dp[s - num] descending, then offer the bitset form (bits |= bits << num) as the one-line speedup and explain why bit T is the answer.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewDoes a subset sum to exactly T?Numbers reusable or once each?ReusableOnce eachExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursive Include/Exclude
1Hint 1Explore hintHide hint
Look at the LAST number. You either include it in the subset or you don't. What target remains in each case?
2Hint 2Explore hintHide hint
Exclude it: still need to make T from the first n-1 numbers. Include it (only if num ≤ rem): need to make rem - num from the first n-1.
3Hint 3Explore hintHide hint
can(i, rem) = can(i-1, rem) OR can(i-1, rem - num[i]). Base: rem == 0 → true; i < 0 → (rem == 0).
A · Core idea
Decide the numbers one at a time, from the last index down. For number i there are two futures: exclude it and try to form the same rem from numbers 0..i-1, or include it (only when num[i] <= rem) and try to form rem - num[i] from 0..i-1. The answer is the OR of those two — a subset exists if either branch can finish the job.
The mental shift: a yes/no reachability question, decided one element at a time. Unlike knapsack's max, there's nothing to optimize here — we only care whether some path reaches rem == 0. So we combine the two branches with logical OR: if any sequence of include/exclude decisions zeroes out the remaining target, the whole thing is true.
Why the include branch recurses on `i-1`. Moving to the previous index after taking number i is what enforces 'each element at most once' — the same number can never be picked again. Recursing on i instead would allow reuse (the unbounded variant).
Why the guard `num[i] <= rem`. Including a number bigger than the remaining target would drive rem negative, which can never come back to 0 with positive numbers — so we simply don't take that branch.
The base cases. rem == 0 means we've already hit the target exactly — return true immediately, even with numbers to spare. Running out of numbers with rem > 0 is false.
Why we don't ship this. The same (i, rem) state recurs through many include/exclude orderings — exponential overlap on two small state variables. Cache it and the blowup collapses to O(n·T).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 4, 5, 2], T = 9can(3, 9)
exclude → can(2,9); include 2 → can(2,7)
branches outtrueC · Code with teaching comments
Reference implementation previewpublic boolean subsetSum(int[] nums, int T) { return can(nums, nums.length - 1, T); } private boolean can(int[] nums, int i, int rem) {Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The state is two numbers — how many elements remain to decide and how much target is left — and the naive tree recomputes the same (i, rem) repeatedly. Two bounded state variables plus heavy overlap is the textbook signal for an O(n·T) DP; the only difference from knapsack is OR instead of max.
ComplexityO(2ⁿ) time, O(n) space — Each number forks into include/exclude, so the recursion tree has up to 2ⁿ leaves, each doing O(1) work. Recursion depth is O(n).
E · Edge cases and pitfalls4T = 0 — can(i, 0) returns true immediately — the empty subset works.Explore edge casesHide edge cases
Edge cases handled
T = 0can(i, 0) returns true immediately — the empty subset works.
Pitfalls
- Recursing on i (not i-1) in the include branch — allows reuse, solving a different problem.
- Using AND or max instead of OR — this is a feasibility question, so OR the branches.
- Skipping this approach — the include/exclude recurrence is what the interviewer wants to hear first.
Approach 2 of 3
Top-Down Memoization on (index, remaining target)
1Hint 1Explore hintHide hint
can(i, rem) returns the same boolean every call. Cache it in a 2-D table indexed by index and remaining target.
2Hint 2Explore hintHide hint
Use a memo of size n × (T+1); store a tri-state (unknown / true / false) since the answer is boolean.
3Hint 3Explore hintHide hint
memo[i][rem] = can(i-1, rem) OR can(i-1, rem - num[i]); fill it before returning so each state is solved once.
A · Core idea
Keep the include/exclude recurrence but cache can(i, rem) so each (index, remaining target) is solved exactly once. Because the result is boolean, use a tri-state memo (unknown / true / false) — Integer/Boolean objects with null in Java, or @lru_cache in Python.
The mental shift: the answer depends only on (i, rem). Whatever include/exclude path led here, the question 'can the first i numbers make rem?' has a fixed answer. Caching by (i, rem) collapses all the duplicate subtrees, and the number of distinct states — n × (T+1) — is the time bound.
Why the state is two-dimensional. As in 0/1 knapsack (and unlike Coin Change), the answer depends on both how many numbers remain and the remaining target — which numbers are still available changes what's reachable. So the memo needs both axes.
Why a tri-state, not a plain boolean default. A default false can't be distinguished from 'computed and found false', so you'd recompute false states forever. Mark cells unknown until filled (e.g. null).
A language note worth saying out loud. The top-down version recurses up to n deep. In Java that's fine for n ≤ 200. In Python the default recursion limit is about 1000, so deep top-down DP can raise RecursionError on large n — which is exactly why the bottom-up boolean table (next approach) is the safer default in Python and also unlocks the bitset speedup.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 5, 11, 5], T = 11can(3, 11)
exclude → can(2,11); include 5 → can(2,6)
memo emptytrueC · Code with teaching comments
Reference implementation previewpublic boolean subsetSum(int[] nums, int T) { Boolean[][] memo = new Boolean[nums.length][T + 1]; return can(nums, nums.length - 1, T, memo); } Explore the full codeHide the full code
D · Why it works and complexityO(n·T) timeO(n·T) spaceOpen the invariant and proofExplore the proofHide the proof
Same mechanical DP upgrade as every problem here: a correct recurrence plus a cache keyed on the true state, (index, remaining target). The boolean objective just means the cached value is a yes/no, and the table size is your complexity.
ComplexityO(n·T) time, O(n·T) space — There are n × (T+1) distinct (i, rem) states, each resolved once in O(1) → O(n·T) time. The memo is O(n·T); recursion depth is O(n) on top.
E · Edge cases and pitfalls5T = 0 — can(i, 0) returns true immediately — empty subset.Explore edge casesHide edge cases
Edge cases handled
T = 0can(i, 0) returns true immediately — empty subset.T larger than the array totalEvery path runs out of numbers with rem > 0 → false, cached cheaply.
Pitfalls
- Defaulting the memo to false instead of a separate 'unknown' marker — recomputes false states.
- Sizing the memo as T instead of T+1 — sums 0..T need T+1 columns.
- Deep recursion in Python (depth ~n) can exceed the ~1000 recursion limit — tabulation avoids the stack.
Approach 3 of 3 · Optimal
Bottom-Up Boolean DP + Bitset Trick (Optimal)
1Hint 1Explore hintHide hint
Make dp[s] = true if some subset sums to s. dp[0] = true; everything else false.
2Hint 2Explore hintHide hint
For each number, update dp[s] = dp[s] OR dp[s - num] for s from T down to num. Descending order keeps each number single-use.
3Hint 3Explore hintHide hint
Speedup: represent the whole dp[] row as the bits of one big integer. Then dp[s] |= dp[s - num] for all s at once is just bits |= (bits << num). Bit T of the final integer is the answer.
A · Core idea
Build reachability from the ground up. dp[s] is true when some subset sums to exactly s. Anchor dp[0] = true (the empty subset), then fold in numbers one at a time: a sum s becomes reachable if it was already reachable or if s - num was reachable before this number was added (then adding num lands on s). That's dp[s] = dp[s] OR dp[s - num]. The answer is dp[T].
Why the 1-D sweep must go DESCENDING — the crux. With a single dp[] array, when we process a number we must read dp[s - num] as it was before this number was folded in. Iterating s from T down to num guarantees dp[s - num] still holds the pre-number value, so each number contributes to a sum at most once. Sweep ascending and dp[s - num] may already include the current number, letting it be reused — that's the unbounded / Coin-Change-II variant, a different problem. This is the exact same loop-direction rule as 0/1 knapsack.
Why dp[0] = true is load-bearing. Every reachable sum is built by adding numbers onto the empty subset. If dp[0] were false, no sum could ever flip to true and the answer would always be false. That single anchored cell makes the whole array meaningful.
The bitset trick. Notice the update dp[s] |= dp[s - num] is the same shift applied to every s. So pack the entire row into one big integer where bit s means 'sum s reachable'. Adding a number is then a single operation: bits |= bits << num shifts every reachable sum up by num and ORs it back in — performing all T updates at once. After processing every number, check bit T: (bits >> T) & 1. Python's arbitrary-precision integers make this trivial; in Java a BigInteger does the same. It's the same O(n·T) work, but the machine handles ~64 sums per word, giving a large constant-factor speedup.
Why no descending worry with the bitset. The shift-and-OR builds a fresh value from the old bits, so it inherently uses the pre-number state — there's no in-place left-to-right hazard to guard against.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 4, 5, 2], T = 9Array state
init
only sum 0 reachable
trueC · Code with teaching comments
D · Why it works and complexityO(n·T) timeO(T) spaceOpen the invariant and proofExplore the proofHide the proof
Subset Sum is 0/1 knapsack with the objective swapped from max-value to boolean reachability — and the descending sweep is the shared signature of 'each item once'. The bitset reformulation is the portable trick worth memorizing: when a DP row is a set of reachable integers updated by a constant shift, a big-integer bits |= bits << k does the whole row in one instruction. The same boolean skeleton solves Partition Equal Subset Sum and underlies Target Sum.
ComplexityO(n·T) time, O(T) space — The outer loop runs n times, the inner sum loop up to T → O(n·T) time, O(T) space for a single boolean row. The bitset form does the same O(n·T) bit operations but processes ~64 sums per machine word, so it's roughly T/64 times faster in practice.
E · Edge cases and pitfalls6T = 0 — dp[0] = true returned directly — empty subset.Explore edge casesHide edge cases
Edge cases handled
T = 0dp[0] = true returned directly — empty subset.a single num equals TFolding that number sets dp[T] = dp[0] = true.T exceeds total of all numbersdp[T] never flips → false (the bitset simply never sets bit T).
Pitfalls
- Sweeping the sum ASCENDING — reuses numbers, answering the unbounded variant instead of 0/1.
- Forgetting dp[0] = true — then no sum is ever reachable and the answer is always false.
- In Java, using a fixed-width long as the bitset when T > 63 — overflow; use BigInteger (or a long[] bitset) for T up to 10⁴.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean subsetSum(int[] nums, int T) { boolean[] dp = new boolean[T + 1]; dp[0] = true; for (int num : nums) { for (int s = T; s >= num; s--) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Ascending sum sweep reuses numbers
Iterating s low-to-high updates dp[s - num] before you read it, so the same number folds in twice — that's the unbounded variant. Descending order preserves the pre-number values.
Explore the code comparisonHide the code comparison
Ascending sum sweep reuses numbers
Iterating s low-to-high updates dp[s - num] before you read it, so the same number folds in twice — that's the unbounded variant. Descending order preserves the pre-number values.
Don't write this
for (int num : nums) {
for (int s = num; s <= T; s++) { // ASCENDING — allows reuse
dp[s] = dp[s] || dp[s - num];
}
}Write this instead
for (int num : nums) {
for (int s = T; s >= num; s--) { // DESCENDING — each number once
dp[s] = dp[s] || dp[s - num];
}
}2Missing dp[0] = true
Every reachable sum is built by adding numbers onto the empty subset. If dp[0] starts false, the OR never has a true to propagate and dp[T] stays false for every input.
Explore the code comparisonHide the code comparison
Missing dp[0] = true
Every reachable sum is built by adding numbers onto the empty subset. If dp[0] starts false, the OR never has a true to propagate and dp[T] stays false for every input.
Don't write this
dp = [False] * (T + 1) # dp[0] never set
for num in nums:
for s in range(T, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[T]Write this instead
dp = [False] * (T + 1)
dp[0] = True
for num in nums:
for s in range(T, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[T]3Fixed-width bitset overflow
A single Java long holds only 64 bits, so 'bits |= bits << num' silently drops sums above 63. For T up to 10⁴ you need BigInteger (or an explicit long[] of ceil((T+1)/64) words).
Explore the code comparisonHide the code comparison
Fixed-width bitset overflow
A single Java long holds only 64 bits, so 'bits |= bits << num' silently drops sums above 63. For T up to 10⁴ you need BigInteger (or an explicit long[] of ceil((T+1)/64) words).
Don't write this
long bits = 1L;
for (int num : nums) bits |= bits << num; // overflows for T > 63
return ((bits >> T) & 1L) == 1L;Write this instead
java.math.BigInteger bits = java.math.BigInteger.ONE;
for (int num : nums) bits = bits.or(bits.shiftLeft(num));
return bits.testBit(T);Revise
Carry the pattern into the interview
Pattern to remember
0/1 knapsack feasibility — boolean reachable-sums DP
Code pattern to memorize
dp[0] = true; dp[1..T] = false
for num in nums:
for s from T down to num:
dp[s] = dp[s] OR dp[s - num]
return dp[T]Rules to remember
- 1It's a boolean DP:
dp[s]answers 'is sumsreachable by some subset?' — you OR possibilities together, you don't add counts. - 2Sweep the sum DESCENDING (
T → num) in the 1-D version so each number is used at most once. Ascending would allow reuse (that's the unbounded/coin-change-II variant). - 3Anchor
dp[0] = true— the empty subset sums to 0. Every reachable sum chains back to this. - 4Once
dp[T]becomes true you can stop early; and ifTexceeds the total of all positives it's instantly false. - 5The bitset trick packs the whole
dp[]row into one integer:bits |= bits << numdoes allTOR-updates in a single shift, and bitTof the result is the answer.
Use this pattern when
- Pure yes/no: does a subset hit an exact target sum?
- Partitioning a set into two equal-sum halves (target = total / 2)
- Reachability over sums rather than optimizing a value
- n and T are small enough that O(n·T) is affordable (pseudo-polynomial)
Choose another pattern when
- You need the COUNT of subsets hitting T → counting DP (sum of ways, not OR)
- Numbers reusable any number of times → unbounded variant, sweep ascending
- You must return the actual subset → track parent pointers / backtrack the table
- T is astronomically large → O(n·T) infeasible; try meet-in-the-middle (O(2^{n/2}))
Interview takeaway
Subset Sum is 0/1 knapsack with the objective swapped from 'max value' to 'is it reachable?'. The boolean recurrence dp[s] |= dp[s - num], swept descending, is the skeleton behind Partition Equal Subset Sum, Target Sum, and Last Stone Weight II. The bitset shift (bits |= bits << num) is the trick that makes it blazingly fast in practice.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 0/1 knapsack feasibility — boolean reachable-sums DP. Recognize it whenever the question is 'can a subset hit an exact sum?' with each element used once. The descending sweep marks it as 0/1, and the same skeleton powers Partition Equal Subset Sum, Last Stone Weight II, and (with OR→sum) the counting variants. The bitset shift is the practical speedup.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Partition Equal Subset SumComing soonSubset Sum with T = total / 2 (and total must be even) — the canonical application of this boolean DP.
- Target SumComing soonAssign +/− signs to every number — reduces to counting subsets with a fixed sum, a counting cousin of this DP.
- Last Stone Weight IIComing soonMinimize the difference of two groups — find the reachable subset sum closest to total / 2.
- Count of Subsets with Sum TComing soonSwap the boolean OR for an integer sum: dp[s] += dp[s - num], counting subsets instead of testing existence.