Katkat
Back

Pick Budget Line Items That Net to an Exact Target

ConfluentSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A staged algorithm discussion: decide whether some subset of budget line items nets to an exact target amount, first with only charges and then with refunds (negative amounts) mixed in, then produce one such subset, then every distinct subset, reasoning about dynamic programming, pruned backtracking, and why negative values change the problem.

You're given a list of integers amounts, each one a budget line item (a positive charge, or a negative refund/credit), and an integer target. A selection is a subset of the line items whose amounts sum to exactly target. Two selections are the same if they contain the same multiset of amounts, regardless of which original entries they came from or what order they're listed in.

The interview built this up in stages: first decide if a selection exists when every amount is a positive charge, then again once refunds (negative amounts) are allowed, then produce one selection, then every distinct selection, and finally discuss how to make it fast.

Settle this before coding

The prompt doesn't say whether the same line item can be picked more than once. Decide this up front: here, each line item may be used at most once — they're distinct ledger entries, not reusable denominations. Note explicitly where your reasoning would change if repetition were allowed instead.

Clarifying questions

  • Can amounts contain duplicate values (e.g., two separate $50 charges), and does the empty selection count when target is 0?
  • How many line items might there be, and how large can an individual amount or target get? (This decides whether a DP table over sums is practical or whether you need to fall back on search.)
  • For "every distinct selection," should near-duplicate selections that differ only by which identical-valued entry was chosen be collapsed into one?

Part 1 — Charges only: does a selection exist?

Restrict amounts so every entry is a positive whole-cent charge, with no refunds, and require target to be zero or greater. Decide, with a True/False answer, whether such a selection can be found.

Part 2 — Charges and refunds: does a selection exist?

Lift that restriction: amounts is free to mix positive charges with negative refunds, and target is no longer bounded to be non-negative. Determine existence again under these looser rules, and pinpoint precisely which guarantee from your Part 1 solution no longer holds.

Part 3 — Produce one selection

Return one selection (as a list of amounts) that sums to target, or indicate that none exists.

Part 4 — Produce every distinct selection

Return every distinct selection summing to target, with no duplicates, even when amounts has repeated values.

Worked example

amounts = [40, -10, 25, -10, 5], target = 20. Valid selections include [40, -10, -10], [25, -10, 5], and [25, -10, 5] picked via the other -10 entry — the last two are the same selection ([25, -10, 5], after sorting) and must appear only once in Part 4's output.

Hints

Hint 1

For Part 1, think in terms of which sums from 0 up to target become reachable as you consider line items one at a time — that reachable-sums view is the whole algorithm.

Hint 2

For Part 2, ask specifically which guarantee your Part 1 method relied on because every amount was non-negative: does a sum only ever grow as you add more items?

Hint 3

For Part 3, you don't need to enumerate everything — stop and return as soon as one path reaches exactly zero remaining target.

Hint 4

For Part 4, sort first and skip over equal values at the same decision point in your search, so two line items with the same amount don't produce two copies of the same selection.

Follow-up questions

  • How would your Part 2 approach need to change if amounts could be very large but `n` stayed small — does a different algorithm become preferable?
  • If line items could repeat, how would you adapt the DP from Part 1 and Part 2 to an unbounded (reuse-allowed) version?
  • How would you extend Part 4 to return only the selections with the fewest line items, among all that sum to target?
  • What's the simplest change to detect that the number of distinct selections is about to explode, so you can bail out with a count or a sample instead of enumerating everything?