Combination Sum

Solution

Backtracking

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    res = []
    # remain, curr cand, i in candidates
    def backtrack(remain, cand, i):
        if remain == 0:
            res.append(cand[:])
            return
        elif remain < 0:
            return
        
        for idx in range(i, len(candidates)):
            cand.append(candidates[idx])
            backtrack(remain - candidates[idx], cand, idx)
            cand.pop()

    backtrack(target, [], 0)
    return res