Problem Brief
Reach Target Balance
FULLTIMEOA
Given a list of numbers, each representing a bank account transaction (positive for credit, negative for debit), determine if there exists a subset of transactions that sums exactly to a given target balance.
Return 1 if such a subset exists, 0 otherwise.
Follow-up: Start with the O(2^n) subset enumeration approach, then optimize toward a dynamic programming solution. Be prepared to discuss the upper bound on n for which each approach is practical (e.g. the O(2^n) solution is feasible up to roughly n ≈ 25).
1Example 1
Input
transactions = [1,2,3], target = 5
Output
1
Explanation
The subset {2, 3} sums to 5. Return 1 (true).
2Example 2
Input
transactions = [1,2], target = 4
Output
0
Explanation
Possible subsets and their sums: {} = 0, {1} = 1, {2} = 2, {1,2} = 3. None equal 4. Return 0 (false).