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

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. ```hint 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. ``` #### 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. ```hint 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 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. ``` #### 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. ```hint 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. ``` #### 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. ```hint 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 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. ``` #### 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. ```hint 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. ``` #### 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 ### What a Strong Answer Covers - The repetition rule, duplicates and the empty-collection case settled before coding - A correct algorithm for every step, each with its complexity - A clear account of why negative numbers invalidate the positive-only shortcuts - Enumeration that produces each solution once and never explores branches that cannot succeed - Optimizations chosen from the actual input sizes rather than listed generically ### 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?