class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        rlt = []
        path = []
        right = len(candidates)

        if right == 0:
            return rlt
        candidates.sort()
        self.sumcal(candidates, 0, right, path, rlt, target, 0)
        return rlt

    def sumcal(self, candidates, begin, end, path, rlt, target, sumnow):
        if sumnow == target:
            rlt.append(path[:])
            return
        
        for index in range(begin, end):
            if index != begin and candidates[index] == candidates[index-1]:
                continue
            sumnow = sumnow + candidates[index]
            if sumnow > target:
                break
            elif sumnow < target and index == end:
                break
            path.append(candidates[index])
            self.sumcal(candidates, index + 1, end, path, rlt, target, sumnow)
            path.pop()
            sumnow = sumnow - candidates[index]