Medium · Pruned Backtracking
Understand → Visualise → Practice.
Return unique nondecreasing combinations that sum to target; each distinct candidate may be reused.
Sort the candidates. At each step choose a candidate at or after the current index (so combinations stay non-decreasing), subtract it from the target, and stop when a candidate exceeds what is left.
Sorting allows early stopping and non-decreasing order.
For i from start, if candidates[i] ≤ remaining, append it and recurse with the same i (reuse allowed).
When remaining reaches 0, save the path; break as soon as a candidate is too large.
Exponential in the target in the worst case; recursion depth at most target / smallest candidate.
Recursing with i + 1 forbids reuse; recursing from 0 creates duplicates in different orders.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.