Combination Sum

Medium· backtracking· combinations

Problem

Given distinct positive candidates and a target, list every unique combination of candidates that adds up to the target. The same candidate may be used any number of times. Two combinations are the same if they use the same numbers with the same counts.

Examples

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

Output: [[2,2,3],[7]]

Input: candidates = [2,3,5], target = 8

Output: [[2,2,2,2],[2,3,3],[3,5]]

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40, all distinct
• 1 <= target <= 40

Hints & approach

Hint 1

To avoid listing [2,3] and [3,2] separately, only ever pick candidates at or after the last one you picked.

Hint 2

Because reuse is allowed, recurse with the same start index after choosing a candidate.

Hint 3

Sort first so you can stop the loop once a candidate exceeds the remaining target.

Approachtry the hints first

Backtrack with (start, remaining, path). If remaining is 0, record the path. Otherwise try each candidate from start onward: if it exceeds remaining, stop (candidates are sorted); else push it and recurse with the same index, since it may be reused, and the reduced remaining. Pop after the call returns. Restricting choices to indices >= start makes every combination non-decreasing, which eliminates duplicate orderings for free.

Time O(n^(T/m)), T = target, m = smallest candidate · Space O(T/m) recursion depth

← PreviousPermutations Next →Letter Combinations of a Phone Number