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
bool subsetReaches(std::vector<int> invoices, int payment) {
}Worked examples
| Call | Result |
|---|---|
subsetReaches(std::vector<int>{3, 34, 4, 12, 5, 2}, 9) | true |
subsetReaches(std::vector<int>{3, 34, 4, 12, 5, 2}, 30) | false |
subsetReaches(std::vector<int>{}, 0) | true |
subsetReaches(std::vector<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++
bool subsetReaches(std::vector<int> invoices, int payment) {
if (payment < 0) return false;
std::set<int> reachable{0};
for (int invoice : invoices) {
std::vector<int> totals(reachable.begin(), reachable.end());
for (int total : totals) {
int next = total + invoice;
if (next <= payment) reachable.insert(next);
}
}
return reachable.count(payment) > 0;
}