关于golang:Leetcode专题数组40组合总和II

力扣链接：
https://leetcode-cn.com/probl…
解题思路：

1. 这道题跟 39- 组合总和 https://segmentfault.com/a/11… 有相似之处，然而不同点导致这道题的难道实际上是更大的，上面一一剖析
2. 首先跟 39 题相似之处在于，这道题也是回溯法的经典案例，应用的解法雷同
3. 不同之处在于：（1）这道题规定数组中的所有数字只能应用一次，那么在进行回溯的时候，start 的下标每次要从可选列表的 i + 1 算起（2）这道题中有反复的数字，然而反复数字也是仅仅只能够应用一次（3）组合之间不能反复，这个是这道题的重点，在剪枝的时候，组合不能反复，还原成树形构造的时候，其实是每层之间不反复，然而树枝上能够反复，这里独自应用一个数组记录对应的下标是否被应用，依据 https://programmercarl.com/00… 题解的剖析，当 nums[i] == nums[i – 1] && used[i-1]= 0 时，表明这个数被上一个组合应用过，那么为了防止层之间反复，须要剪掉

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
    }
}