Problems › TypeScript › patterns
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
Where you start
function subsetReaches(invoices: number[], payment: number): boolean {
}Worked examples
| Call | Result |
|---|---|
subsetReaches([3,34,4,12,5,2], 9) | true |
subsetReaches([3,34,4,12,5,2], 30) | false |
subsetReaches([], 0) | true |
subsetReaches([], 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 TypeScript
function subsetReaches(invoices: number[], payment: number): boolean {
if (payment < 0) return false;
const reachable = new Set<number>([0]);
for (const invoice of invoices) {
for (const total of Array.from(reachable)) {
const next = total + invoice;
if (next <= payment) reachable.add(next);
}
}
return reachable.has(payment);
}