题解 | #加起来和为目标值的组合(二)#

class Solution:
    def combinationSum2(self, num: List[int], target: int) -> List[List[int]]:
        # write code here
        num.sort()
        n = len(num)
        res, g = [], []
		##递归求解
        def get_s(n, num, target,  g, res, begin):
            if sum(g) == target:
                res.append(g.copy())
            for i in range(begin, n):
                ##剪枝处理
				if i>begin and num[i]==num[i-1]:
                    continue
                if sum(g) + num[i] <= target:
                    g.append(num[i])
                    get_s(n, num, target,  g, res, i + 1)
                    #回溯
					g.pop()
            return res

        return get_s(n, num, target, g, res, 0)