Katkat
Back

Pick Numbers Summing to a Target: Existence With Negatives, One and All Solutions

ConfluentSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A staged coding discussion about choosing integers from a list so that they add up to a target. It asks whether a solution exists with only positive numbers and then with mixed signs, for one solution and for every solution without duplicates, and for optimizations, testing dynamic programming, pruned backtracking and reasoning about negative numbers.

You are given a list of integers nums and an integer target. A solution is a collection of numbers taken from nums whose sum is exactly target. The order in which the numbers are listed does not matter: [2, 3] and [3, 2] are the same solution.

The interviewer built the question up in steps: decide whether any solution exists when every number is positive, decide it again when nums contains both positive and negative numbers, return one solution, return all solutions, and finally discuss optimizations.

Constraints and Clarifications

  • The source does not say whether a number may be used more than once. Settle this before you start, and say where your answers differ between the two rules.
  • Input sizes and value ranges are not given. Ask for them, because they decide which approaches are practical.

Clarifying Questions

  • May each number be used any number of times, or at most once per occurrence in nums?
  • Can nums contain duplicate values or zeros?
  • If target is 0, does the empty collection count as a solution?
  • How long can nums be, and how large can target and the values be?

Part 1 — All numbers positive: does a solution exist?

Every number in nums is a positive integer, and target is a non-negative integer. Return whether at least one solution exists.

What This Part Should Cover

  • A correct decision procedure for the agreed repetition rule
  • Time and space complexity in terms of the list length and the target, and why the bound is pseudo-polynomial
  • Early exits that positivity makes possible

Part 2 — Positive and negative numbers: does a solution exist?

Now nums may contain both positive and negative integers, and target may be any integer. Return whether a solution exists, and explain what breaks in your Part 1 approach.

What This Part Should Cover

  • The Part 1 assumptions that fail: the range of partial sums, and pruning once the running sum passes the target
  • A correct procedure when each number is used at most once, with the range of sums it must track
  • What changes when reuse is allowed, including whether the answer simplifies
  • Edge cases: zeros, a target of zero, and lists whose numbers all have the same sign

Part 3 — Return one solution

Return the numbers of one solution, or report that none exists, for both the all-positive and the mixed-sign case.

What This Part Should Cover

  • Reconstructing a solution from the existence computation with little extra memory
  • A bounded search for the mixed-sign case that is guaranteed to terminate
  • Respecting the agreed repetition rule in the returned collection

Part 4 — Return all solutions

Return every solution exactly once.

What This Part Should Cover

  • Duplicate-free enumeration, including duplicate values in the input
  • Pruning that is valid only for positive numbers, and what replaces it with negative numbers
  • Whether the set of solutions is finite under each repetition rule
  • Running time stated relative to the size of the output

Part 5 — Optimization

Discuss how to make the previous parts faster or lighter on memory.

What This Part Should Cover

  • Faster forms of the dynamic program, such as bit-parallel updates
  • Input reductions such as removing duplicates and dividing out a common factor
  • Alternatives for a huge target, or for a short list with huge values
  • Memory savings for the existence, single-solution and enumeration tables

Hints

Hint 1

Smaller targets first: Ask which smaller sums would have to be reachable for `target` to be reachable, and how many distinct sums can matter at all.

Hint 2

What positivity bought you: List every assumption your Part 1 method relied on because the numbers were positive, and check which of them still hold.

Hint 3

One of each sign: If numbers may be reused, ask which totals you can build from a single positive number and a single negative number.

Hint 4

Walk back from the target: If your existence check filled a table, ask what one extra fact per entry would let you trace a reachable `target` back to the numbers that produced it.

Hint 5

One order per collection: Pick a generation order under which each collection can be produced in only one way, including when `nums` holds equal values.

Hint 6

Avoid dead branches: Ask how a precomputed table could tell you, before you recurse, whether the remaining amount can still be completed with the numbers you are still allowed to use.

Hint 7

Which size is large?: Decide whether the list length, the target or the magnitude of the values is the large quantity, and choose techniques whose cost does not grow with it.

Follow-up questions

  • How would you count the solutions without listing them, and how does the count change if different orders count as different solutions?
  • Each number may be used at most once, `nums` has 40 elements, and values can be as large as one billion. Which approach would you use?
  • How would you return the solution that uses the fewest numbers?
  • You must answer existence for many different targets against the same `nums`. What would you precompute?