Problem · Dynamic Programming
Reach Target Balance
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).
Examples
01 · Example 1
transactions = [1,2,3] target = 5 return = 1
The subset {2, 3} sums to 5. Return 1 (true).
02 · Example 2
transactions = [1,2] target = 4 return = 0
Possible subsets and their sums: {} = 0, {1} = 1, {2} = 2, {1,2} = 3. None equal 4. Return 0 (false).
More Confluent problems
public int canReachBalance(int[] transactions, int target) {
// write your code here
}
transactions[1,2,3]
target5
expected1
sign in to submit