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
Java 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
boolean subsetReaches(List<Integer> invoices, int payment) {
}Worked examples
| Call | Result |
|---|---|
subsetReaches(Main.<Integer>ls(3, 34, 4, 12, 5, 2), 9) | true |
subsetReaches(Main.<Integer>ls(3, 34, 4, 12, 5, 2), 30) | false |
subsetReaches(Main.<Integer>ls(), 0) | true |
subsetReaches(Main.<Integer>ls(), 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 Java
boolean subsetReaches(List<Integer> invoices, int payment) {
if (payment < 0) return false;
Set<Integer> reachable = new HashSet<>();
reachable.add(0);
for (int invoice : invoices) {
for (Integer total : new ArrayList<>(reachable)) {
int next = total + invoice;
if (next <= payment) reachable.add(next);
}
}
return reachable.contains(payment);
}