vvrf / DSA.log

问题拆解

从一组互不相同的正整数里选数，使总和等于 target，同一个数可以选任意多次，返回所有不重复的组合。

朴素的想法是每一层递归都从头枚举所有候选数，凑够了就收集。这样做会把 [2, 3, 2] 和 [2, 2, 3] 当成两个答案——它们只是顺序不同的同一个组合。事后用集合去重既费空间又费时间，更好的办法是从一开始就不生成重复。

去重的诀窍是给候选数组规定一个处理顺序：递归带一个 start 下标，每层只从 start 往后枚举。一旦某层选了 candidates[i]，之后的所有层都不再碰 i 之前的数。为什么这样不漏解？因为任何一个组合都可以按候选的下标顺序排好写出来（比如先写所有的 2 再写所有的 3），这个“规范形态”一定会被搜索到；而 [3, 2, 2] 这类乱序形态被禁止回头选 2 而生成不出来——每个组合恰好保留一个代表。

组合 = 不在乎顺序的选择。给选择强加一个全序，规定“只准往后选”，重复就从源头上消失了，这比生成后再去重优雅得多。

按 start 递归的回溯

“同一个数可无限次使用”落实在一个细节上：选了 candidates[i] 之后，递归传入的 start 仍是 i（允许下一层再选它），而不是组合题常见的 i + 1。先把数组排序，剩余额度小于当前候选时可以直接剪掉整条右侧分支。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates); // 排序后才能按“候选变大”剪枝
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, target, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) {
            break; // 已排序，后面的更大，整支剪掉
        }
        path.add(candidates[i]);
        backtrack(candidates, remain - candidates[i], i, path, res); // 传 i：当前数还能再选
        path.remove(path.size() - 1);
    }
}

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()  # 排序后才能按“候选变大”剪枝
    res = []
    path = []

    def backtrack(remain: int, start: int) -> None:
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break  # 已排序，后面的更大，整支剪掉
            path.append(candidates[i])
            backtrack(remain - candidates[i], i)  # 传 i：当前数还能再选
            path.pop()

    backtrack(target, 0)
    return res

func combinationSum(candidates []int, target int) [][]int {
    slices.Sort(candidates) // 排序后才能按“候选变大”剪枝
    res := [][]int{}
    path := []int{}
    var backtrack func(remain, start int)
    backtrack = func(remain, start int) {
        if remain == 0 {
            res = append(res, slices.Clone(path))
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remain {
                break // 已排序，后面的更大，整支剪掉
            }
            path = append(path, candidates[i])
            backtrack(remain-candidates[i], i) // 传 i：当前数还能再选
            path = path[:len(path)-1]
        }
    }
    backtrack(target, 0)
    return res
}

pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    fn backtrack(
        candidates: &[i32], remain: i32, start: usize,
        path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>,
    ) {
        if remain == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] > remain {
                break; // 已排序，后面的更大，整支剪掉
            }
            path.push(candidates[i]);
            backtrack(candidates, remain - candidates[i], i, path, res); // 传 i：当前数还能再选
            path.pop();
        }
    }
    let mut candidates = candidates;
    candidates.sort_unstable(); // 排序后才能按“候选变大”剪枝
    let mut res = Vec::new();
    backtrack(&candidates, target, 0, &mut Vec::new(), &mut res);
    return res;
}

start 传 i 还是 i + 1 是这一族题的分水岭：传 i 表示“当前数还可以继续选”（本题），传 i + 1 表示“每个数最多选一次”（组合总和 II）。混淆两者是最常见的错。另外剪枝分支用 break 而不是 continue——正因为排过序，第一个超出剩余额度的候选之后全都超，直接停掉整层循环。

复杂度

指标	复杂度	原因
时间	`O(S)`，S 为搜索树节点数	最坏是指数级（如全 1 凑 target），剪枝决定实际规模
空间	`O(target / min)`	递归深度最深是全用最小候选凑 target

可以迁移的模式

组合类回溯用 start 下标固定候选顺序，“只往后选”让每个组合只有一种生成方式；
“元素可重复选”与“最多选一次”只差递归时传 i 还是 i + 1；
先排序，再在循环里对“单调超标”的候选整支 break，是搜索题性价比最高的剪枝。

想明白 start 的语义，组合总和 II、子集、组合这一整族题就只是同一个模板改参数。