Backtrack with remaining target. Start from current index to avoid duplicates.
function combinationSum(candidates, target): result = [] def backtrack(index, current, remaining): if remaining == 0: result.append(current[:]) return if remaining < 0: return for i in range(index, len(candidates)): current.append(candidates[i]) backtrack(i, current, remaining - candidates[i]) current.pop() backtrack(0, [], target) return result
Time varies by output size.