组合总和 II · 一次性宝石配方工坊

怎样从“candidates=[1,2,2,5], target=5，每张卡用一次，求和为 5 的组合。”推导出 回溯 · 去重组合，并证明每次状态变化都不会漏掉答案？

中心结论：中央配方炉需要 target=5 点能量。桌上 candidates=[1,2,2,5] 是一次性宝石卡：每张卡只能投入一次。两张 2 标成 2A、2B——它们可以同时进配方 [1,2,2]；但根层若已从 2A 开局，就不能再从 2B 重复开局（同层去重）。

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

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

在本站主例中，candidates=[1,2,2,5],target=5,每张卡用一次,求和为5的组合。

算法最终需要得到或观察：[[1,2,2], [5]]。

先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 path、start、i、同层去重。
3. 3转移每一步按照 中央配方炉需要 target=5 点能量。桌上 candidates=[1,2,2,5] 是一次性宝石卡：每张卡只能投入一次。两张 2 标成 2A、2B——它们可以同时进配方 [1,2,2]；但根层若已从 2A 开局，就不能再从 2B 重复开局（同层去重）。
4. 4收尾读取 [[1,2,2], [5]]。，并复核边界与复杂度。

路径记录已做选择，候选集合决定下一步，撤销保证兄弟分支互不污染。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：path、start、i、同层去重。

题目要求出总和为 sum 的所有组合，组合需要去重。这一题是第 39 题的加强版，第 39 题中元素可以重复利用(重复元素可无限次使用)，这一题中元素只能有限次数的利用，因为存在重复元素，并且每个元素只能用一次(重复元素只能使用有限次) 这一题和第 47 题类似。

排序后同层 skip 相同值起点;每个下标最多选一次,dfs(i+1);和==target 收集。

执行过程中持续维护：path、start、i、同层去重。

正确性依赖以下不变量：同层不重复选相同值,避免重复组合。

面试时可以压缩为：排序+同层去重+每个数一次,标准回溯模板。

落到当前题，执行机制可以压缩为：中央配方炉需要 target=5 点能量。桌上 candidates=[1,2,2,5] 是一次性宝石卡：每张卡只能投入一次。两张 2 标成 2A、2B——它们可以同时进配方 [1,2,2]；但根层若已从 2A 开局，就不能再从 2B 重复开局（同层去重）。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1candidates=[1,2,2,5], target=5第一屏看懂：一次性宝石卡 + 目标和。 因为：LC40 每个下标最多用一次；LC39 才允许同一数字反复投入。
2. 2sort → [1,2A,2B,5]宝石卡按面值排列到轨道。 因为：排序让相同值相邻，才能判断当前值是不是同层重复值。
3. 3选 2A, remain→2在 [1] 后面接上第一张 2。 因为：下一层从 i+1=2 开始，2B 仍可选。
4. 4remain==0 → collect两张 2 同时合法入配方。 因为：[1,2,2] 是合法答案。跳过规则只发生在同一层：i > start && nums[i] == nums[i-1]。
5. 55>remain → break此分支不可能凑满 5。 因为：排序后更大候选直接 break。
6. 6i>start && nums[i]==nums[i-1]2B 分支变灰冻结，不进入递归。 因为：同层重复起点会产生重复组合，不是禁止两张 2 同时用。
7. 7return ans展示最终答案仓库。 因为：回溯枚举 + 同层去重 + i+1 一次性使用。
8. 8LC40 回溯模板串联全部关键概念。 因为：排序 O(n log n)；回溯最坏接近 O(2^n·n)，递归栈 O(n)，不计答案存储。模板：remain==0 收集；for i:=start；同层 skip 重复值；>remain break；dfs(i+1,...)；path.pop()。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"sort"
)

func combinationSum2(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	sort.Ints(candidates) // 这里是去重的关键逻辑
	findcombinationSum2(candidates, target, 0, c, &res)
	return res
}

func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) {
	if target == 0 {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	for i := index; i < len(nums); i++ {
		if i > index && nums[i] == nums[i-1] { // 这里是去重的关键逻辑,本次不取重复数字，下次循环可能会取重复数字
			continue
		}
		if target >= nums[i] {
			c = append(c, nums[i])
			findcombinationSum2(nums, target-nums[i], i+1, c, res)
			c = c[:len(c)-1]
		}
	}
}

func main() {
    // 1. 主例
    //    输入：mode="combination-sum", nums=[1,2,2,5], target=5
    //    期望：[[1,2,2], [5]]。
    //
    // 2. 失败 / 未命中
    //    检查：只去重 start 不够,要同层 skip 相同值。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC39 组合总和；LC90 子集 II
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意candidates=[1,2,2,5], target=5，每张卡用一次，求和为 5 的组合。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化中央配方炉需要 target=5 点能量。桌上 candidates=[1,2,2,5] 是一次性宝石卡：每张卡只能投入一次。两张 2 标成 2A、2B——它们可以同时进配方 [1,2,2]；但根层若已从 2A 开局，就不能再从 2B 重复开局（同层去重）。
4. 4证明同层不重复选相同值,避免重复组合。
5. 5复杂度时间 最坏接近 O(2^n·n)，排序 O(n log n)，空间 递归栈 O(n)，不计答案存储