Micro-Drill #189 — Combination sum (reuse allowed)

def combinationSum(candidates, target):
    res = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1
            path.pop()
    candidates.sort()
    backtrack(0, [], target)
    return res