算法

组合总和

loser

08 Sep 2026 • 6 min read

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合。

candidates 中的同一个数字可以无限制重复选取。如果至少一个数字的选取数量不同，则两种组合不同。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 + 2 + 3 = 7，7 = 7。

示例 2：

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入：candidates = [2], target = 1
输出：[]

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

回溯：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());

        vector<vector<int>> ans;
        vector<int> path;
        backtrack(candidates, target, 0, path, ans);
        return ans;
    }

private:
    void backtrack(vector<int>& candidates, int remain, int start, vector<int>& path, vector<vector<int>>& ans) {
        if (remain == 0)
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); ++i)
        {
            if (candidates[i] > remain)
            {
                break;
            }

            path.push_back(candidates[i]);
            backtrack(candidates, remain - candidates[i], i, path, ans);
            path.pop_back();
        }
    }
};

核心思想

这题需要枚举所有和为 target 的组合，可以使用回溯。

和普通子集问题不同，这里有两个关键点：

同一个数字可以被重复选择。
不同组合不能因为顺序不同而重复出现。

例如 [2,2,3] 和 [2,3,2] 在这道题中属于同一种组合，不能都加入答案。

因此，回溯时需要让路径中的数字下标保持非递减：

当前选择 candidates[i] 后，下一层仍然从 i 开始选

这样既允许重复选择当前数字，又不会回头选择更靠前的数字，从而避免排列顺序导致的重复。

回溯状态

递归函数定义为：

void backtrack(vector<int>& candidates, int remain, int start, vector<int>& path, vector<vector<int>>& ans)

其中：

remain：当前还需要凑出的剩余目标和。
start：当前这一层可以从哪个下标开始选择。
path：当前已经选择的组合。
ans：保存所有合法组合。

初始时：

backtrack(candidates, target, 0, path, ans);

表示还需要凑出 target，并且可以从下标 0 开始选择任意候选数。

递归终止条件

当 remain == 0 时，说明当前路径中的数字之和正好等于 target：

if (remain == 0)
{
    ans.push_back(path);
    return;
}

此时将 path 加入答案。

因为每次选择数字都会让 remain 减小，所以当 remain 变为 0 时就已经形成了一个完整组合。

为什么下一层从 `i` 开始

代码中的递归调用是：

backtrack(candidates, remain - candidates[i], i, path, ans);

注意最后一个参数传的是 i，不是 i + 1。

这是因为题目允许同一个数字重复使用。

例如 candidates = [2,3,6,7]，target = 7：

选择 2 后，下一层仍然可以继续选择 2

这样才能得到组合 [2,2,3]。

如果传 i + 1，每个数字就只能使用一次，不符合题意。

为什么不会产生重复组合

虽然数字可以重复使用，但回溯过程中始终保持下标不下降。

也就是说，一个组合只能按照候选数组中的顺序生成。

例如在排序后的数组 [2,3,6,7] 中：

可以生成 [2,2,3]
不会生成 [2,3,2]
不会生成 [3,2,2]

因为一旦选择了下标更靠后的 3，下一层就不能再回头选择下标更靠前的 2。

所以每种组合只会被生成一次。

排序与剪枝

代码先对 candidates 排序：

sort(candidates.begin(), candidates.end());

排序后，如果当前候选数已经大于剩余目标和：

if (candidates[i] > remain)
{
    break;
}

那么后面的数字只会更大，也不可能凑出合法组合，可以直接结束当前循环。

这个剪枝不会影响正确性，只是减少无效搜索。

正确性证明

结论 1：算法生成的每个组合之和都等于 `target`

递归过程中，每选择一个数字 candidates[i]，都会将 remain 减去这个数字。

只有当 remain == 0 时，算法才会把当前路径加入答案。

因此，加入答案的每个组合，其元素和都正好等于初始的 target。

结论 2：算法生成的每个组合都符合题目要求

递归调用下一层时传入的是 i，所以当前数字可以在后续继续被选择，满足同一个数字可以无限重复使用的要求。

同时，下一层只能从当前下标 i 或更靠后的下标继续选择，因此路径中的候选下标始终非递减。

所以算法生成的是合法组合，而不是把同一组数字的不同排列重复计入答案。

结论 3：所有合法组合都会被生成

任意一个合法组合，都可以按照候选数组排序后的下标从小到大排列。

算法在每一层都会从 start 开始枚举所有可选候选数，并且选择下标 i 后，下一层仍然允许从 i 开始继续选择。

因此，对于任意合法组合中的每一个数字，算法都能按照其非递减下标顺序依次选出。

所以所有合法组合都会被生成。

结论 4：算法不会生成重复组合

算法要求路径中的候选下标始终非递减。

同一个组合按非递减下标排列后只有一种生成顺序。

因此，一个组合不会因为元素排列顺序不同而被重复生成。

综上，算法能够正确返回所有和为 target 的不同组合。

示例分析

以 candidates = [2,3,6,7]，target = 7 为例：

选择 2，remain = 5
继续选择 2，remain = 3
继续选择 2，remain = 1，无法继续
回退，选择 3，remain = 0，得到 [2,2,3]

回到第一层，选择 3，remain = 4，无法凑出 4
选择 6，remain = 1，无法继续
选择 7，remain = 0，得到 [7]

最终返回：

[[2,2,3],[7]]

复杂度分析

设 n 为 candidates 的长度，target 为目标和，minValue 为候选数组中的最小值。

时间复杂度：与合法组合和搜索树规模有关，最坏情况下可近似看作 O(n^(target / minValue))。题目保证答案数量少于 150，实际搜索规模较小。
空间复杂度：O(target / minValue)。递归深度最多为 target / minValue。如果计入返回结果，空间复杂度还需要加上所有组合占用的空间。

边界情况

最小候选数大于 target：循环会被剪枝直接结束，返回空数组。
某个候选数等于 target：可以单独构成一个组合。
需要重复使用同一个数字：递归时传入 i，因此可以连续选择同一个候选数。
candidates 原本无序：先排序，不影响组合本身，只用于剪枝和避免重复生成排列。

回溯：