Leetcode专题[数组]-40-组合总和II golang

【Leetcode专题[数组]-40-组合总和II】力扣链接：
https://leetcode-cn.com/probl...
解题思路：

这道题跟39-组合总和https://segmentfault.com/a/11...有相似之处，但是不同点导致这道题的难道实际上是更大的，下面一一分析
首先跟39题相似之处在于，这道题也是回溯法的经典案例，使用的解法相同
不同之处在于：（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 } }