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

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

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

        def dfs(idx, target):

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

            i = idx

            while(i < len(candidates)):

                if target < candidates[i]:
                    break

                else:
                    candi.append(candidates[i])
                    dfs(i+1, target - candidates[i])
                    candi.pop(-1)

                while i < len(candidates)-1 and candidates[i] == candidates[i+1]:
                    i+=1

                i+=1

        dfs(0, target)
        return res