Algorithms and Data Structures · Middle · Question 75 of 75
Subset sum: can some of the numbers add up to target? What is the classic DP solution?
- 1Sort the numbers and greedily take the largest that still fit
- 2Try all permutations of the numbers and check their sums
- ✓Correct answer: A boolean table of reachable sums, updated for each number: O(n × target)
Explanation
reachable[s] says whether sum s can be formed; for each number, update sums from high to low so it's used once. Greedy can miss solutions, and permutations are O(n!). The DP is pseudo-polynomial: fast only while target is small.