Subset sum equal to target
HardTake or skip, indexed by remaining target
Problem
Return whether a subset of the array sums exactly to a target.
Track every reachable subset sum; the target is possible if it appears among them.
The idea
The state is (index, remaining target) and the answer is whether skipping or taking the current element can finish. Because the target is bounded, the table is O(n × target) rather than exponential.
The trick
- Iterate the sum downward when using a 1-D array, or an element gets reused.
- Base: target 0 is reachable by taking nothing.
- Pseudo-polynomial — it depends on the target's magnitude.
items4
Step 1 of 6. Brute force: for each of the 4 items, branch into "skip it" or "take it". items 4.
1/6
Brute force
timeO(2ⁿ)spaceO(n)
2ⁿ decision tree.
1function go(i, sum) {2 if (i === n) return sum === target;3 return go(i + 1, sum) || go(i + 1, sum + nums[i]);4}Input
- nodes
- 1, 0 edges
Memory
- items
- 4
- branches
- —
- subsets
- —
Call stack
- 0visit(start)
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 4], target = 6
- Output:
- true
- Explanation:
- 2+4 (or 1+2+3) makes 6.
Example 2
- Input:
- nums = [1, 2, 7], target = 6
- Output:
- false
- Explanation:
- No subset sums to 6 → false.
Example 3
- Input:
- nums = [5], target = 5
- Output:
- true
- Explanation:
- The single 5 works.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.