刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

思路

这道题跟39很相似，差别就在于本题
1、数组内元素会重复
2、每个数字在每个组合中只能使用一次
而39题中
1、无重复元素
2、每个元素可以多次使用

这个差距主要就体现在剪枝方法中了

• 首先是这里不能重复使用同一元素，这个相对简单，只要保证搜索的起始位置持续往后推进即可
• 其次一点，本次数组中会有重复元素，原本这里我是使用了map来记录使用情况，但是这个实现很复杂，因为要使用记录会根据深度产生变化。后来借鉴了精选答案中的一个方式，很是精妙：

对于同一层级来说，相同的元素得到的结果集一定是重复的，所以可以直接砍掉相同层级中后续相同元素的子树

代码

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	return do(candidates, target, 0, len(candidates))
}

func do(candidates []int, target, start, end int) [][]int {
	res := make([][]int, 0)
	for k, num := range candidates {
		if k < start {
			continue
		}

		if num > target {
			break
		}
        // 砍掉相同层级，相等兄弟节点的子树
		if k > start && candidates[k] == candidates[k-1] {
			continue
		}

		if num == target {
			res = append(res, []int{num})
			break
		}

		resTemp := []int{num}
		resLoop := do(candidates, target-num, k+1, end)
		for _, resLoopItem := range resLoop {
			temp := append(resTemp, resLoopItem...)
			res = append(res, temp)
		}
	}
	return res
}