class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        #Time Complexity: O(len(candidates)^target)
        #Space Complexity: O(target)

        res = []
        candi = []
        candidates.sort()

        def dfs(idx, target):

        #    if target < 0:
        #        return 
            if target == 0:
                res.append(candi.copy())
                return

            for i in range(idx, len(candidates)):
                if target >= candidates[i]:
                    candi.append(candidates[i])
                    dfs(i, target - candidates[i])
                    candi.pop(-1)

        dfs(0, target)
        return res