Combination Sum

Find all unique combinations of numbers that sum to a target.

backtracking recursion combinations sorting

Write a function `combination_sum(candidates: List[int], target: int) -> List[List[int]]` that returns all unique combinations of `candidates` where the chosen numbers sum to `target`. You may use each candidate an unlimited number of times. The solution set must not contain duplicate combinations. The input list may be unsorted. The output must be a list of combinations, where each combination is a list of integers sorted in non-decreasing order. The overall order of combinations in the output must be lexicographically sorted (compare combinations element by element, as Python would when sorting a list of lists). For example, `[[3, 8], [5, 3, 3]]` is invalid because each combination is not non-decreasing; the correct output is `[[3, 3, 5], [3, 8]]` after sorting the result list. The function signature is `def combination_sum(candidates: List[int], target: int) -> List[List[int]]:`. You may use `from typing import List`.

Constraints

- 1 <= len(candidates) <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct.
- 1 <= target <= 500
- The number of unique combinations is less than 150.
- You may use each candidate unlimited times.

Example

>>> combination_sum([2,3,6,7], 7)
[[2, 2, 3], [7]]
>>> combination_sum([2,3,5], 8)
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
>>> combination_sum([2], 1)
[]

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the candidates first; this helps generate combinations in non-decreasing order without duplicates.

Use recursion that always starts from the current index (allowing repeats) to build combinations.

Base cases: if remaining == 0, record the current combination; if remaining < 0, prune.

After collecting all combinations, sort the outer list lexicographically to meet the required output order.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.