Given an array of distinct positive integers candidates and a positive target, return all unique combinations of candidates that add up to target. The same number may be used any number of times. Two combinations are the same if they use each number the same number of times, regardless of order. Return them in any order.
2 + 2 + 3 = 7 and 7 = 7. No other combination works.- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All candidates are distinct
- 1 <= target <= 40
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force could generate every sequence of candidates up to the target and keep the sorted, de-duplicated ones that sum correctly, but it explores the same combination in many orders. The fix is to choose candidates in non-decreasing index order: once we move past index j, we never go back to it. That gives each combination exactly one path in the recursion tree. Since a number can repeat, the recursive call starts again at j, not j + 1. Sorting lets us prune: if candidates[j] is already larger than what remains, every later candidate is too.
Algorithm
- Sort
candidates. - Define
backtrack(start, remaining): ifremaining == 0, record a copy ofpath. - Loop
jfromstart; break whencandidates[j] > remaining. - Append
candidates[j], callbacktrack(j, remaining - candidates[j]), then pop. - Call
backtrack(0, target)and return the result.
O(N^(T/M + 1)) in the worst case, T = target, M = smallest candidateSpace: O(T/M) recursion depth, plus the outputj + 1 instead of j silently turns this into "each number at most once" and loses answers like [2,2,3]. Combination Sum II (with duplicates, each used once) is the classic follow-up: recurse with j + 1 and skip equal siblings.class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() # lets us stop early res, path = [], []Β def backtrack(start, remaining): if remaining == 0: res.append(path[:]) return for j in range(start, len(candidates)): c = candidates[j] if c > remaining: break # sorted: the rest are too big path.append(c) backtrack(j, remaining - c) # j again: reuse allowed path.pop()Β backtrack(0, target) return res