You are given candidates, a list of distinct positive integers, and a positive integer target.
Return every combination of candidates that adds up to exactly target. You may use each
candidate as many times as you like.
Two combinations are the same if they use every candidate the same number of times, so [2, 3]
and [3, 2] are one combination: list each combination once. The combinations, and the numbers
inside each one, may come in any order. If nothing adds up to target, return an empty list.
Example 1
- Input
- candidates = [2, 3, 5, 9], target = 9
- Output
- [[9], [2, 2, 5], [2, 2, 2, 3], [3, 3, 3]]
Example 2
- Input
- candidates = [3, 4, 7], target = 10
- Output
- [[3, 7], [3, 3, 4]]
Example 3
- Input
- candidates = [4], target = 3
- Output
- []
Constraints
candidatesholds 1 to 30 distinct numbers, each between 2 and 40.- 1 ≤
target≤ 40 - The answer holds fewer than 150 combinations.
Show the pattern
Backtracking
You must list every way to reach a total, and each pick narrows what is left to reach. Backtracking tries a pick, explores what follows, and undoes it, giving up on a branch as soon as the total is passed.
See backtracking in a visualiserShow the approach
Sort a copy of the candidates, then backtrack with the combination being built, chosen, and the
amount still needed, remaining. explore(start, remaining):
- saves a copy of
chosenwhenremainingis 0; - otherwise tries each candidate from index
startonwards: append it, explore(i, remaining − candidate), then pop it.
Passing i rather than i + 1 lets a candidate repeat, and never going back to an earlier index
builds each combination in one order only, so it appears once. Because the candidates are sorted,
the loop can stop at the first one bigger than remaining: every later one is bigger still.
Time: Exponential: up to n choices at each of t / m levels, for target t and smallest candidate m · Space: O(t / m) for the recursion, besides the output