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.
subsetReaches(invoices: list<int>, payment: int) → bool
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func subsetReaches(invoices []int, payment int) bool {
}Worked examples
| Call | Result |
|---|---|
subsetReaches([]int{3, 34, 4, 12, 5, 2}, 9) | true |
subsetReaches([]int{3, 34, 4, 12, 5, 2}, 30) | false |
subsetReaches([]int{}, 0) | true |
subsetReaches([]int{}, 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 Go
func subsetReaches(invoices []int, payment int) bool {
if payment < 0 {
return false
}
reachable := map[int]bool{0: true}
for _, invoice := range invoices {
totals := []int{}
for total := range reachable {
totals = append(totals, total)
}
for _, total := range totals {
next := total + invoice
if next <= payment {
reachable[next] = true
}
}
}
return reachable[payment]
}