回溯法求解 0/1 子集和
0/1 子集和问题（Subset Sum）的核心任务是判断：给定一组元素，是否存在一个子集，其元素之和恰好等于目标值。约束条件是每个元素最多被选取一次。
这里需要区分两个概念：判定存在性（Decision Problem）与枚举所有解（Witness Enumeration）。前者只需回答“是/否”，后者需要输出所有满足条件的组合，输出规模通常远大于前者。
针对正整数场景，通过排序可以引入有效的剪枝策略：
def subset_sum_witnesses(values: list[int], target: int) -> list[list[int]]:
values = sorted(values)
result: list[list[int]] = []
path: list[int] = []
def visit(start: int, remaining: int) -> None:
if remaining == 0:
result.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])
visit(i + 1, remaining - values[i])
path.pop()
visit(0, target)
return result
代码中的两个关键细节：
start索引递增：确保每个位置只被使用一次（0/1 约束），并维持组合的规范顺序。- 同层去重：
if i > start and values[i] == values[i - 1]: continue。在回溯树的同一深度，跳过与上一个节点相同的值，从而消除由重复元素产生的冗余解（即相同的值多重集）。
边界与陷阱
- 剪枝的前提：
values[i] > remaining的剪枝逻辑仅在所有值为正数时成立。如果存在负数，当前值过大不代表后续组合无法通过负数抵消，此时该剪枝无效。 - 递归参数：递归调用时传入
i + 1是 0/1 背包/子集和的标志。若传入i，则允许元素无限次重复使用，问题性质变为完全背包或无限制子集和。 - 排列 vs 组合：子集和关注的是“选了哪些元素”，而非“选取顺序”。生成子集的排列（Permutations）不属于子集和问题范畴，顺序变化不应被视为新解。
复杂度分析
- 回溯法：最坏情况下需探索 个子集，时间复杂度为指数级。
- 动态规划：对于非负整数目标，若仅需判定存在性，可使用伪多项式时间的 DP 算法，复杂度为 ，其中 为目标值。这本质上是利用数值范围（Magnitude）换取状态空间的大小。
解的跟踪与输出成本
输入 [1,1,2,3]，目标 4。先选 1 后剩 3；再选第二个 1 后剩 2，找到 [1,1,2]；若第二步改选 3，则找到 [1,3]。根层跳过第二个 1，否则会重复同样的值多重集。从 2 开始的分支无法再用剩余的 3 补齐，被剪掉。因此完整输出为 [[1,1,2],[1,3]]。
正整数输入下，目标零恰有空解 [[]]，负目标没有解，空输入也遵循此规则。零不在此实现约定内：剩余值为零时立即返回，会漏掉 [0] 等延伸。负数也破坏提前返回和剪枝论证，例如 [-3,-2] 可凑成 −5，尽管排序后第一个值已大于目标。若允许正负数，应按位置做选或不选的递归，在末尾检查总和，或另外证明适用于有符号数的上下界。
索引递增使深度最多为 n。含排序副本和栈的辅助空间为 O(n)；保存和复制解在最坏情况下还需 O(n·2ⁿ) 时间与输出空间。前述 O(nT) 判定 DP 不仅要求目标为非负整数，也要求物品值为非负整数。
assert subset_sum_witnesses([1, 1, 2, 3], 4) == [[1, 1, 2], [1, 3]]
assert subset_sum_witnesses([], 0) == [[]]
assert subset_sum_witnesses([], 1) == []