刷题使我快乐，满脸开心.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

思路

题意理解

这道题最大的难点就在这俩句话：

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

也就是说，每个数字（而不是每种数字）都可以且仅可以使用一次，因为candidates 没有说明不包含重复数字。这一点在示例中也得到了体现

  • 注意：解集不能包含重复的组合。
    虽然独立的数字可以自由组合，但是存在相同的数字时，得到的结果很可能是相同的。我们需要避免这种情况

解题思路

总体就是回溯的思路，关键在于重复数字的选择问题上了，我的方法如下:

  • 先排序，简化操作
  • 在排序的前提下，转换一个概念，重复数字并非不能选，而是要在每个遍历层级上不能选择重复的。

进入下一个遍历层级时，就可以选择相同数字了。排序的情况下，相当于结果集中的每个顺位上，不能再选择一样的数字了。

思路还是挺简单的，细节在注释~

代码

func combinationSum2(candidates []int, target int) [][]int {
	// 先排序，便于去重处理
	sort.Ints(candidates)
	n := len(candidates)
	results := make([][]int, 0)
	var find func(result []int, restTarget, index int)
	find = func(result []int, restTarget, index int) {
		// 不符合的选择，或者已经没得数字可选了，直接返回
		if restTarget < 0 || index > n {
			return
		}

		// 符合要求的记录结果
		if restTarget == 0 {
			// result 传递的是指针，隔绝此机制影响
			temp := make([]int, 0)
			temp = append(temp, result...)
			results = append(results, temp)
		}

		// 尝试遍历
		for i := index; i < n; i++ {
			// i > index 有两个作用，
			// 一是 防止 candidates[i-1] 越界
			// 二是 同一层级不再选择相同数字（并非不能选相同数字，而是在不同层级去选）
			if i > index && candidates[i] == candidates[i-1] {
				continue
			}
			// 选择数字去尝试
			result = append(result, candidates[i])
			find(result, restTarget-candidates[i], i+1)
			// 回溯
			result = result[:len(result)-1]
		}
	}
	find(make([]int, 0), target, 0)
	return results
}

作者：LittleStone
链接：https://leetcode.cn/problems/combination-sum-ii/solutions/2657620/shu-ju-biao-xian-yi-ban-dan-shi-gan-jue-9zpff/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。