Комбинация сумм II

Сложность: Средняя 

Условие задачи: На входе имеем список возможных кандидатов и целевое значение суммы, необходимо вывести все комбинации, которыми можно получить целевое значение. 

Каждое число из списка кандидатов должно содержаться в конечном подсписке из ответов ровно один раз.

Результирующий ответ не должен содержать в себе дубликатов. 

Пример:

Ввод: candidates = [10,1,2,7,6,1,5], target = 8

Вывод: [

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

Ввод: candidates = [2,5,2,1,2], target = 5

Вывод: [

[1,2,2],

[5]

]

class Solution:
        
    def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
        
        def dfs(i, path, current_target):
            if(current_target == 0): # target was reached
                ans.append(path[:])
            else:
                for j in range(i,len(nums)):
                    if(j!=i and nums[j-1] == nums[j]):  # remove the duplicates
                        continue

                    if(current_target < nums[j]):
                        break

                    dfs(j+1, path + [nums[j]], current_target - nums[j])
            
        ans = []
        nums.sort()
        dfs(0,[],target)
        return ans