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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def combinationSum2(self , num: List[int], target: int) -> List[List[int]]:
        # write code here

        path = []
        num.sort()
        
        def backtrack(res, combination, start):
            #注意res小于0的情况放到最前面，这种情况的概率远大于res等于0的情况
			#不得不服，等于0放前面真的会超时
            if res < 0:
                return
            elif res == 0:
                path.append(combination.copy())
				#这里没写return，但其实有无没啥关系
            else:
                for i in range(start, len(num)):
                    #去重
                    if i > start and num[i] == num[i-1]:
                        continue
                    combination.append(num[i])
                    backtrack(res - num[i], combination, i + 1)
                    combination.pop()
            
        backtrack(target, [], 0)

        return path