Golang задача. Комбинация сумм 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]

]

Решение

import (
    "sort"
)

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    combos := make([][]int, 0)
    
    var dfs func([]int, int, []int)
    dfs = func(nums []int, targ int, path []int) {
        if targ < 0 {
            return
        }
        if targ == 0 {
            combos = append(combos, path)
            return
        }
        
        for i, n := range nums {
            if i > 0 && nums[i] == nums[i-1] {
                continue
            }
            newPath := make([]int, len(path))
            copy(newPath, path)
            dfs(nums[i+1:], targ-n, append(newPath, n))
        }
        return
    }
    
    dfs(candidates, target, []int{})
    return combos
}