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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def combinationSum2(self , num: List[int], target: int) -> List[List[int]]:
        num.sort()
        n = len(num)
        res, path = [], []
        vis = [False]*n
        def dfs(x:int,c:int):
            if c==0:
                res.append(path.copy())
                return
            for y in range(x,n):
                if not vis[y] and num[y]<=c:
                    if y>0 and num[y]==num[y-1] and not vis[y-1]:
                        continue
                    vis[y] = True
                    path.append(num[y])
                    dfs(y+1,c-num[y])
                    path.pop()
                    vis[y] = False
            
        dfs(0,target)
        return res