Backtracking explores choices while restoring state after each branch. Pruning is correct only when the excluded branch cannot lead to a valid answer.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: Stop a combination branch when its remaining capacity cannot satisfy the target under stated assumptions. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Represent partial choices
Keep mutable path state with a clear restore operation.
Step 2: Prove the excluded bound
A prune must rule out every continuation under stated assumptions.
Step 3: Restore after recursion
One branch’s choices must not contaminate its siblings.
Worked scenario
Stop a combination branch when its remaining capacity cannot satisfy the target under stated assumptions.
With positive candidates, a partial sum above the target cannot return downward by adding more positive values. If negative candidates are permitted, that prune is no longer safe. Likewise, duplicate-value handling and reuse rules change which branches represent distinct valid solutions.
Common mistake
A pruning rule based on positive numbers may fail with negative inputs.
Verify the behavior
Test the exact-bound case and a counterexample after relaxing each assumption.
Interview exercise
Prove a prune is safe.
Answer and reasoning
Show the bound rules out every continuation, then test boundary cases where the best possible continuation exactly meets the target.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.