FastPrep
Problem · Dynamic Programming

Reach Target Balance

Learn this problem
● MediumConfluent logoConfluentFULLTIMEOA

Problem statement

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).

Function

canReachBalance(transactions: int[], target: int) → int

Examples

Example 1

transactions = [1,2,3]target = 5return = 1
The subset {2, 3} sums to 5. Return 1 (true).

Example 2

transactions = [1,2]target = 4return = 0
Possible subsets and their sums: {} = 0, {1} = 1, {2} = 2, {1,2} = 3. None equal 4. Return 0 (false).

More Confluent problems

drafts saved locally
public int canReachBalance(int[] transactions, int target) {
  // write your code here
}
transactions[1,2,3]
target5
expected1
checking account