Subsets & Combinations - Combination Sum (Reuse Allowed)
The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:
def combinationSum(candidates, target):
candidates.sort()
result = []
def backtrack(index, path, target):
if target == 0:
result.append(path[:])
return
if index == len(candidates) or target < 0:
return
max_use = target // candidates[index]
for count in range(max_use + 1):
path += [candidates[index]] * count
backtrack(index + 1, path, target - candidates[index] * count)
# Missing path restoration here
backtrack(0, [], target)
return result