LeetCode 39. 组合总和

◎

本节目标

排序候选数后按剩余目标剪枝，并允许从当前下标重复选择同一候选数。

这道题将回溯决策树的组合模板扩展为可重复选择：每个候选数可使用多次，但每个结果仍只保留一种递增构造顺序。

查看 LeetCode 原题

题意与约束

给定互不相同的正整数候选数组和目标值 target，找出和为目标值的所有组合。相同候选数可以无限次使用，答案中的组合顺序不计差异。

朴素思路与瓶颈

若每次都从第一个候选数重新选择，会同时得到 [2, 3, 2]、[3, 2, 2] 等同一组合的排列。若先生成任意长度序列再求和，超过目标的分支也会无意义地继续扩展。

剩余目标与可重复选择

先把候选数升序排列。递归状态由剩余目标 remaining 和起始下标 start 组成：选择 candidates[index] 后，下一层仍传 index，这就是允许重复使用当前数；但不会回到更小下标，所以每条路径保持非递减，不会产生排列式重复。

当 remaining 为零，当前路径正好是一组答案。若候选数已大于 remaining，因为后面只会更大，循环可以立即停止。这一剪枝来自排序和正整数约束，而不是事后用集合消除重复。

代码实现

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> answer;
    vector<int> path;

    void backtrack(const vector<int>& candidates, int remaining, int start) {
        if (remaining == 0) {
            answer.push_back(path);
            return;
        }

        for (int index = start; index < static_cast<int>(candidates.size()); index++) {
            int candidate = candidates[index];
            if (candidate > remaining) {
                break;
            }
            path.push_back(candidate);
            backtrack(candidates, remaining - candidate, index);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        answer.clear();
        path.clear();
        backtrack(candidates, target, 0);
        return answer;
    }
};

Python

Python 3

class Solution:
    def combinationSum(
        self, candidates: list[int], target: int
    ) -> list[list[int]]:
        candidates.sort()
        answer: list[list[int]] = []
        path: list[int] = []

        def backtrack(remaining: int, start: int) -> None:
            if remaining == 0:
                answer.append(path.copy())
                return

            for index in range(start, len(candidates)):
                candidate = candidates[index]
                if candidate > remaining:
                    break
                path.append(candidate)
                backtrack(remaining - candidate, index)
                path.pop()

        backtrack(target, 0)
        return answer

复杂度分析

设最小候选数为 a、候选数个数为 m。决策树深度最多为 target / a，最坏搜索上界为 O(m^(target / a))；实际时间还必须计入所有答案路径的复制长度。递归栈和当前路径额外占用 O(target / a) 空间，输出空间取决于全部有效组合的总长度。

易错点

• 递归后传 index + 1，错误地把题目改成“每个候选数只能用一次”。
• 不排序就使用“候选数超过剩余目标时停止”，剪枝不再成立。
• 选择后没有弹出路径末尾，使下一个候选分支带入前一分支的数字。

模式迁移

当每个元素只能使用一次时，递归起点改为 index + 1，并需要处理输入中的重复值。目标不再是数值和而是字符串、坐标或容量时，remaining 可替换为相应的剩余资源或未完成约束。