[数据结构与算法]组合总和II-回溯40-python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        # 有重复元素一定要先排序
        candidates = sorted(candidates)
        res = []
        track = []
        trackSum = 0 # 整数加减比sum(track)更快

        def backtrack(start, track):
            nonlocal trackSum
            if trackSum == target:
                res.append(track[:])
                return
            elif trackSum > target:
                return
            
            for cho in range(start, n):
                # 因为元素有重复，所以在此确保被选择过的元素不会再被选择
                # 剪枝操作
                if cho > start and candidates[cho] == candidates[cho-1]:
                    continue

                track.append(candidates[cho])
                trackSum += candidates[cho]
                backtrack(cho+1, track)
                trackSum -= candidates[cho]
                track.pop()
        
        backtrack(0, track)
        return res