40. 组合总和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. 组合总和 的进阶版，唯一的区别是选择自己之后不能在此选择自己了，并且为了使结果集内不重复，选择自己之后不能选择与自己相同元素。

为了更好的判断相同的元素，可以预先给数组排序。

func combinationSum2(candidates []int, target int) (result [][]int) {
	sort.Ints(candidates)
	var dfs func(index, sub int, res []int)
	dfs = func(index, sub int, res []int) {
		if sub == 0 {
			result = append(result, append([]int{}, res...))
			return
		}
		for i := index; i < len(candidates); i++ {
			if i > index && candidates[i] == candidates[i-1] {
				continue
			}
			if sub-candidates[i] >= 0 {
				res = append(res, candidates[i])
				dfs(i+1, sub-candidates[i], res)
				res = res[:len(res)-1]
			}
		}
	}
	dfs(0, target, []int{})
	return result
}

复杂度：

• 时间复杂度：O(O(2^n * n))
• 空间复杂度：O(N)

执行结果：

• 执行耗时:2 ms,击败了59.02% 的Go用户
• 内存消耗:2.5 MB,击败了31.62% 的Go用户