算法刷题系列（三十二）：组合总和——在回溯中处理复用与去重

算法刷题系列（三十二）：组合总和——在回溯中处理复用与去重

组合总和把回溯的几个关键决定放在同一道题里：选择后是否允许重复使用元素、答案中的顺序是否重要、相同候选值会不会造成重复路径。

本文约定候选数是正整数，组合按数值多重集比较（[2, 3, 2] 与 [2, 2, 3] 是同一个组合）。每个候选值可以重复使用。例：候选 [2, 3, 6, 7]、目标 7，答案为 [2, 2, 3] 和 [7]。

状态与剪枝

递归状态由三个量组成：当前搜索起点 start、尚未凑出的 remaining、当前路径 path。在排序后的候选数组中，从 start 起挑数 x：

• 若 x > remaining，由于后面的数更大，后续分支也不可能成立，可以停止这一层循环；
• 递归仍传入当前下标 i，因此 x 可以再次使用；
• 下一次只能从 i 或更大的下标取数，因此组合保持非递减顺序，不会把不同排列重复计数。

当 remaining == 0 时，当前路径就是一个解。若数组中有重复候选值，先排序去重，避免相同数值从不同下标出发形成相同答案。

Java 实现

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class CombinationSumSearch {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (target < 0) {
            throw new IllegalArgumentException("target must be non-negative");
        }
        TreeSet<Integer> unique = new TreeSet<>();
        for (int value : candidates) {
            if (value <= 0) {
                throw new IllegalArgumentException("candidates must be positive");
            }
            unique.add(value);
        }
        int[] values = unique.stream().mapToInt(Integer::intValue).toArray();
        List<List<Integer>> answer = new ArrayList<>();
        search(values, 0, target, new ArrayList<>(), answer);
        return answer;
    }

    private static void search(
        int[] values, int start, int remaining,
        List<Integer> path, List<List<Integer>> answer
    ) {
        if (remaining == 0) {
            answer.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < values.length; i++) {
            int value = values[i];
            if (value > remaining) {
                break;
            }
            path.add(value);
            search(values, i, remaining - value, path, answer);
            path.remove(path.size() - 1);
        }
    }
}

Python 实现

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    if target < 0:
        raise ValueError("target must be non-negative")
    if any(value <= 0 for value in candidates):
        raise ValueError("candidates must be positive")

    values = sorted(set(candidates))
    answer: list[list[int]] = []
    path: list[int] = []

    def search(start: int, remaining: int) -> None:
        if remaining == 0:
            answer.append(path.copy())
            return
        for index in range(start, len(values)):
            value = values[index]
            if value > remaining:
                break
            path.append(value)
            search(index, remaining - value)
            path.pop()

    search(0, target)
    return answer

assert combination_sum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
assert combination_sum([2, 2, 3], 0) == [[]]

正确性与复杂度

每个合法组合都可唯一写成非递减序列。递归按这个序列逐项选择；允许从当前下标继续，保证重复使用；禁止回到更小下标，避免排列重复。达到剩余值为零时收集答案，因此每个合法组合都会被枚举且不会以不同顺序重复出现。

最小候选值为 m 时，路径深度最多 target / m。候选为正保证剩余值严格下降，也保证搜索终止。搜索树和答案数可能呈指数增长，输出本身也可能很大；额外递归空间为 O(target / m)，不计结果。

常见错误与边界

• 忘记正数前提：若允许 0，递归可能无限；若允许负数，按排序剪枝也不再成立。
• 为了复用而传 i + 1：这会变成每个候选最多使用一次；复用版本需要传 i。
• 从 0 重新开始：会生成 [2,3] 与 [3,2] 这样的重复排列。
• 只去重结果：先排序、统一递归顺序并去掉重复候选，通常更简单也更省搜索。
• 目标为零：空组合是有效解，应返回 [[]]；空候选且正目标则返回空列表。

如果题目规定“每个候选只能用一次”，递归起点应改成 i + 1，并在同一层跳过重复值。这一处变化对应的是题意中的资源复用规则，不是随意的模板差异。