39.Combination Sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        path = []
        n = len(candidates)
        # t means left target
        def dfs(i, t):
            if t < 0:
                return
            if t == 0:
                ans.append(path[:])
                return
            for j in range(i, n):
                path.append(candidates[j])
                dfs(j, t-candidates[j])
                path.pop()
        dfs(0, target)
        return ans