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
C# 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
public bool SubsetReaches(List<int> invoices, int payment) {
}Worked examples
| Call | Result |
|---|---|
SubsetReaches(new List<int> { 3, 34, 4, 12, 5, 2 }, 9) | true |
SubsetReaches(new List<int> { 3, 34, 4, 12, 5, 2 }, 30) | false |
SubsetReaches(new List<int> { }, 0) | true |
SubsetReaches(new List<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 C#
public bool SubsetReaches(List<int> invoices, int payment) {
if (payment < 0) return false;
var reachable = new HashSet<int> { 0 };
foreach (var invoice in invoices) {
foreach (var total in new List<int>(reachable)) {
int next = total + invoice;
if (next <= payment) reachable.Add(next);
}
}
return reachable.Contains(payment);
}