Can any of these add up to it
A settlement tool checks whether some combination of outstanding invoices adds up exactly to a payment that came in.
- Each invoice is either used once or left out.
- Every invoice is zero or more.
- Return whether some subset totals exactly the payment.
- A payment of zero is always reachable — by using nothing.
subset_reaches(invoices: list<int>, payment: int) → bool
Where you start
def subset_reaches(invoices: list[int], payment: int) -> bool:
Worked examples
| Call | Result |
|---|---|
subset_reaches([3, 34, 4, 12, 5, 2], 9) | True |
subset_reaches([3, 34, 4, 12, 5, 2], 30) | False |
subset_reaches([], 0) | True |
subset_reaches([], 5) | False |
Hint
For each invoice there are two worlds: one where you use it and one where you do not. Solve the smaller problem in both, and either one succeeding is enough.
Reference solution in Python
def subset_reaches(invoices: list[int], payment: int) -> bool:
if payment < 0:
return False
reachable = {0}
for invoice in invoices:
for total in list(reachable):
nxt = total + invoice
if nxt <= payment:
reachable.add(nxt)
return payment in reachable