~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Meet in the middle
Split n ~ 40 into two halves of 2^20 and combine with sort + two pointers.
Notes
Recognise it when: n ≈ 40, where 2^40 is too many but 2^20 is fine: subset sums close to a target, or counting subsets that sum to a target.
Split the items into halves. Enumerate all subset sums of each half, sort one list, and for each sum in the other use two pointers or bisect to find the best complement. O(2^(n/2) · n).
4 problems
Advanced & competitive
Search tricks Ternary search, meet in the middle.
Meet in the middle
- Basics: subset sums of two halves basics easy
- Trail mix with two exact targets py · c++ · java easy
- Subset sum closest to a goal py · c++ · java medium
- Count subsets with a target sum py · c++ · java medium