递归函数需要一个清楚的契约：当前调用解决哪个子问题，规模怎样缩小，最小问题返回什么。分治把大问题拆成相对独立的子问题，再合并答案；回溯则在候选决策树上探索，失败后恢复状态，继续下一条分支。
状态必须足以描述剩余问题
从一组正整数中选若干项，使和等于目标，每个位置最多使用一次，返回不同的数值组合。把输入排序后，状态由“下一个可选下标、剩余目标、已经选择的前缀”组成。后续只能从更右侧选，既保证不会重复使用位置，也让组合内部有序。
def combinations_for_sum(values, target):
if target < 0 or any(x <= 0 for x in values):
raise ValueError('target must be non-negative and values positive')
values = sorted(values)
answer, path = [], []
def search(start, remaining):
if remaining == 0:
answer.append(path.copy())
return
for i in range(start, len(values)):
if i > start and values[i] == values[i - 1]:
continue
if values[i] > remaining:
break
path.append(values[i])
search(i + 1, remaining - values[i])
path.pop()
search(0, target)
return answer
if __name__ == '__main__':
print(combinations_for_sum([1, 1, 2, 3], 4))
对 [1,1,2,3]、目标4，结果是 [1,1,2] 与 [1,3]。同一层遇到与前一候选相同的值时跳过，防止两个“选一个1”的等价分支；更深一层仍允许选择另一个1，所以 [1,1,2] 不会被漏掉。
append 后递归，再 pop，两步共同维护选择前缀。保存答案时使用 path.copy()，否则所有结果会引用同一个后续被修改的列表。递归返回后前缀必须恢复为调用前的状态，这是回溯的核心不变量。
剪枝依赖前提
排序后若当前值已经超过剩余目标，后面的值也不会适合，可直接停止这一层搜索。这一步要求候选全为正数；允许负数时，“已经超出目标”并不意味着以后不能回来。例子明确拒绝零和负候选，把这一限制写进规格比悄悄漏解更可靠。
没有剪枝时，选或不选形成最多 2^n 个子集；复制输出还要乘上结果长度。当前算法对小规模组合问题合适，不能因为写成短小递归就声称高效。辅助状态除结果外为 O(n)，递归深度也可达到n。大量输入时应先改变问题建模，增加递归深度上限并不会缩小搜索树。
回溯、记忆化和动态规划
若只问“是否存在”或“方案数”，不同路径可能反复到达同一个剩余子问题，可缓存 (index, remaining)。但在生成全部方案时，缓存不能随意忽略不同前缀的输出需求。动态规划把可复用的子问题按依赖关系求解；并非所有回溯都必须改写为DP。
分治的子问题可以是两个不重叠的子数组，回溯的子分支则代表互斥选择；两者都可递归实现，但合并方式、状态恢复和复杂度分析不同。排序中的归并是前者，本例是后者。
练习与面试自查
增加只返回组合数量的函数，比较是否可以用记忆化减少重复。为小输入枚举所有下标掩码，把满足条件的排序元组放入集合，与回溯输出对拍。检查目标为零、空输入、全部重复和无解的情形。
面试中说明三件事：为什么下一层从 i+1 开始；为什么同层去重和全局去重不同；为什么正数剪枝不能搬到任意整数输入。能给出这些理由，比背一份回溯模板更能验证理解。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。