组合总和 · 能量熔炉回溯

怎样从“candidates=[2,3,6,7], target=7，找所有和为 7 的不重复配方（可重复选）。”推导出 回溯 · 组合总和，并证明每次状态变化都不会漏掉答案？

中心结论：能量熔炉需要填满 target 点能量。材料卡片 candidates 库存无限，可重复投入。我们要找所有「不重复配方」——[2,2,3] 与 [7] 合法，但 [2,3,2] 与 [2,2,3] 是同一组合。

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

candidates 中的数字可以无限制重复被选取。

在本站主例中，candidates=[2,3,6,7],target=7,找所有和为 7 的组合(可重复)。

算法最终需要得到或观察：组合 [2,2,3] 与 [7]。

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

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

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 路径 path、剩余 target、start 下标。
3. 3转移每一步按照 能量熔炉需要填满 target 点能量。材料卡片 candidates 库存无限，可重复投入。我们要找所有「不重复配方」——[2,2,3] 与 [7] 合法，但 [2,3,2] 与 [2,2,3] 是同一组合。
4. 4收尾读取 合法配方 [[2,2,3], [7]]。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：路径 path、剩余 target、start 下标。

题目要求出总和为 sum 的所有组合，组合需要去重。 这一题和第 47 题类似，只不过元素可以反复使用。

回溯:排序后选 start,递归选≥当前数,和==target 记录;和>target 剪枝。

执行过程中持续维护：路径 path、剩余 target、start 下标。

正确性依赖以下不变量：path 和单调增,避免 [2,3] 与 [3,2] 重复。

面试时可以压缩为：排序+start 控制重复:递归可重复选同一数,sum>target 剪枝,O(2^n) 上界。

落到当前题，执行机制可以压缩为：能量熔炉需要填满 target 点能量。材料卡片 candidates 库存无限，可重复投入。我们要找所有「不重复配方」——[2,2,3] 与 [7] 合法，但 [2,3,2] 与 [2,2,3] 是同一组合。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1candidates=[2,3,6,7], target=7第一屏应一眼看懂：找所有不重复配方。 因为：LC39 是组合总和，材料可重复使用。
2. 2start 闸门演示 start=1用户能直观看懂 start 如何避免 [2,3] 与 [3,2]。 因为：start 不是普通下标，它是一道禁止回头的闸门。
3. 3再选 2, remain→3演示可重复选同一数字。 因为：传 i 而非 i+1 是 LC39 与 LC40 的关键区别。
4. 4path = path[:len-1]从死路退回上一层。 因为：回溯不是瞎试，而是选择 → 递归 → 撤销选择 → 换下一个选择。
5. 5回溯到 path=[2]继续探索 [2] 的其他分支。 因为：回溯后继续 for 循环下一个 i。
6. 6根层选 3探索以 3 开头的配方。 因为：根层 i=1 选 3，下一层 start=1。
7. 7收集 [7]第二个完整配方。 因为：单材料恰好等于 target。
8. 8回溯模板总结串联全部关键概念。 因为：排序 + start 闸门防排列重复；递归传 dfs(i, remain-candidate) 允许重复选当前数；remain==0 收集，candidate>remain 剪枝。搜索树规模最坏指数级，递归深度约 target/minCandidate。

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

import "sort"

func combinationSum(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	sort.Ints(candidates)
	findcombinationSum(candidates, target, 0, c, &res)
	return res
}

func findcombinationSum(nums []int, target, index int, c []int, res *[][]int) {
	if target <= 0 {
		if target == 0 {
			b := make([]int, len(c))
			copy(b, c)
			*res = append(*res, b)
		}
		return
	}
	for i := index; i < len(nums); i++ {
		if nums[i] > target { // 这里可以剪枝优化
			break
		}
		c = append(c, nums[i])
		findcombinationSum(nums, target-nums[i], i, c, res) // 注意这里迭代的时候 index 依旧不变，因为一个元素可以取多次
		c = c[:len(c)-1]
	}
}

func main() {
    // 1. 主例
    //    输入：mode="combination-sum", nums=[2,3,6,7], target=7
    //    期望：组合 [2,2,3] 与 [7]。
    //
    // 2. 失败 / 未命中
    //    检查：不排序 start 会重复组合。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC40 组合总和 II；LC46 全排列
}

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

1. 1题意candidates=[2,3,6,7], target=7，找所有和为 7 的不重复配方（可重复选）。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化能量熔炉需要填满 target 点能量。材料卡片 candidates 库存无限，可重复投入。我们要找所有「不重复配方」——[2,2,3] 与 [7] 合法，但 [2,3,2] 与 [2,2,3] 是同一组合。
4. 4证明path 和单调增,避免 [2,3] 与 [3,2] 重复。
5. 5复杂度时间 搜索树规模，最坏指数级，空间 递归深度约 target/minCandidate，不计答案空间