Leetcode topic [array] -40- combined sum II

Force link ：
https://leetcode-cn.com/probl...
Their thinking ：

1. This question follows 39- Combinatorial summation https://segmentfault.com/a/11... There are similarities , But is the difference actually bigger , Here's an analysis
2. First with 39 The similarity of the questions lies in , This question is also a classic case of backtracking method , The solution used is the same
3. The difference is ：（1） This problem stipulates that all the numbers in the array can only be used once , So when we go back ,start Every time the subscript of is selected from the optional list i+1 Count up （2） There are repeated numbers in this question , But repeated numbers can only be used once （3） Combinations cannot be repeated , This is the key point of the problem , While pruning , The combination cannot be repeated , When the tree structure is restored , In fact, there is no repetition between each layer , But the branches can repeat , Here, a separate array is used to record whether the corresponding subscript is used , according to https://programmercarl.com/00... Analysis of problem solution , When nums[i] == nums[i - 1] && used[i-1]=0 when , Indicates that this number has been used by the previous combination , So to avoid repetition between layers , It needs to be cut off

func combinationSum2(candidates []int, target int) [][]int {
    res := [][]int{}
    sort.Ints(candidates)
    used := make(map[int]bool)
    backtrack(&res, candidates, []int{}, 0, target, 0, used)
    return res
}

func backtrack(res *[][]int, nums, path []int, sum, target, start int, used map[int]bool) {
    if sum >= target {
        if sum == target {
            newPath := make([]int, len(path))
            copy(newPath, path)
            *res = append(*res, newPath)
        }
        return
    }
    for i := start; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] && used[i-1] == false {
            continue
        } 
        path = append(path, nums[i])
        sum += nums[i]
        used[i] = true
        backtrack(res, nums, path, sum, target, i+1, used)
        path = path[:len(path)-1]
        sum -= nums[i]
        used[i] = false
    }
}