Reuse a number: combination sum

Why it matters

Pricing bundles, reusable resource packs, and recipe combinations can ask which repeated choices reach an exact total. A blind search generates the same combination in different orders and spends time below totals that can no longer be reached. The result must include every valid combination once, allow unlimited reuse, and exclude duplicate orderings.

Candidates are unique. You may reuse a number. Return combinations that sum to target. Sort each combination, then sort the list.

Input

candidates = [2, 3, 6, 7], target = 7

Output

[[2, 2, 3], [7]]

For [2, 3, 6, 7] and target 7, a blind ordered search builds duplicate permutations and overshoots. Keep candidate indexes nondecreasing, so [2, 2, 3] appears but [3, 2, 2] does not, and stop branches whose next value exceeds the remainder.

With candidates [2, 3, 6, 7] and target 7, choose 2 to leave 5, choose 2 again to leave 3, then choose 3 to reach 0 and record [2, 2, 3]. A branch with 1 remaining stops because every allowed candidate is too large.

Each recursive loop starts at the chosen candidate's index. That permits another 2 but never returns to an earlier value, so [3, 2, 2] is not built separately. Back at the root, choosing 7 reaches 0 directly and records the only other answer, [7].