The problem
Given an array of different positive integers candidates and a target, return every combination of candidates that adds up to target. The same number may be used any number of times; two combinations are different if some number is used a different number of times. Any order.
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]]
- Input
candidates = [2], target = 1
- Output
[]
Constraints
- 1 ≤ candidates.length ≤ 30
- 2 ≤ candidates[i] ≤ 40, all different
- 1 ≤ target ≤ 40
The idea
Build a combination by choosing numbers in order of their position: after choosing candidates[i], the next choice may be candidates[i] again or anything after it, never anything before. That order is what stops 2, 3 and 3, 2 both being produced.
Carry what is still needed. At 0, the combination is complete. With the candidates sorted, as soon as one is bigger than what is left, every later one is too — stop trying that branch.
- Time
- O(n^(t/m)) in the worst case — t the target, m the smallest candidate, so no combination is longer than t/m
- Space
- O(t/m) besides the answer
Solution · every language run against every case
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() # so a candidate too big means every later one is too out, cur = [], [] def pick(start, left): # add candidates from index start on; left: what is still needed if left == 0: out.append(cur[:]) return for i in range(start, len(candidates)): if candidates[i] > left: break cur.append(candidates[i]) pick(i, left - candidates[i]) # i, not i + 1: the same number may be used again cur.pop() pick(0, target) return out