组合总和总结

1. 组合总和 I（Combination Sum）

问题描述

• 目标：在一个无重复的候选数字集合 candidates 中，找到所有 可以无限次重复 使用这些数字的组合，使得数字的总和等于目标数 target。
• 要求：
  • 每个数字可以被无限次使用。
  • 所有数字都是正整数。
  • 组合中不允许有重复的组合（顺序不影响）。

示例

• 示例 1：

  • 输入：candidates = [2,3,6,7], target = 7
  • 输出：[[7], [2,2,3]]

• 示例 2：

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

解题思路

• 回溯算法（Backtracking）：

  • 从候选数字中选择一个数字加入当前组合。
  • 由于每个数字可以被无限次使用，在递归调用时可以再次选择当前数字。
  • 当组合的和等于目标时，记录当前组合。
  • 当组合的和超过目标时，回溯。

• 剪枝优化：

  • 在递归过程中，如果当前数字大于剩余的目标和，可以提前停止遍历（因为候选数字通常排序后递增）。

关键点

• 允许重复使用数字：在递归时，下一步可以选择当前数字及之后的数字（startIndex 保持不变或向后移动）。
• 避免重复组合：通过排序和控制递归的起始索引，确保组合的唯一性。

示例代码（C++）

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:vector<vector<int>> res;vector<int> path;void backtrack(vector<int>& candidates, int target, int startIndex, int currentSum){if(currentSum == target){res.push_back(path);return;}if(currentSum > target){return;}for(int i = startIndex; i < candidates.size(); ++i){// 选择当前数字path.push_back(candidates[i]);// 递归调用，允许重复使用当前数字backtrack(candidates, target, i, currentSum + candidates[i]);// 回溯，移除最后一个数字path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 排序，便于剪枝backtrack(candidates, target, 0, 0);return res;}
};

---

2. 组合总和 II（Combination Sum II）

问题描述

• 目标：在一个可能包含重复的候选数字集合 candidates 中，找到所有 每个数字只能使用一次 的组合，使得数字的总和等于目标数 target。
• 要求：
  • 每个数字只能使用一次。
  • 组合中不允许有重复的组合（即使输入中有重复的数字）。

示例

• 示例 1：

  • 输入：candidates = [10,1,2,7,6,1,5], target = 8
  • 输出：[[1,1,6], [1,2,5], [1,7], [2,6]]

• 示例 2：

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

解题思路

• 回溯算法（Backtracking）：

  • 类似于组合总和 I，但每个数字只能使用一次。
  • 在递归调用时，下一步选择从当前数字的下一个位置开始，避免重复使用当前数字。

• 处理重复元素：

  • 首先对 candidates 进行排序。
  • 在递归过程中，如果当前数字与前一个数字相同且前一个数字未被选择，则跳过当前数字，以避免生成重复的组合。

关键点

• 避免重复组合：通过排序和在递归中跳过重复数字，确保每个组合的唯一性。
• 每个数字使用一次：在递归调用时，startIndex 移动到 i + 1，确保每个数字仅被使用一次。

示例代码（C++）

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:vector<vector<int>> res;vector<int> path;void backtrack(vector<int>& candidates, int target, int startIndex, int currentSum){if(currentSum == target){res.push_back(path);return;}if(currentSum > target){return;}for(int i = startIndex; i < candidates.size(); ++i){// 跳过重复的数字if(i > startIndex && candidates[i] == candidates[i-1]){continue;}// 选择当前数字path.push_back(candidates[i]);// 递归调用，移动到下一个数字，避免重复使用backtrack(candidates, target, i + 1, currentSum + candidates[i]);// 回溯，移除最后一个数字path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 排序，便于处理重复backtrack(candidates, target, 0, 0);return res;}
};

---

3. 组合总和 III（Combination Sum III）

问题描述

• 目标：找到所有由 k 个不同 数字（1到9）组成且总和为 n 的组合。
• 要求：
  • 仅使用数字 1 到 9，每个数字最多使用一次。
  • 组合中恰好有 k 个数字。
  • 不允许有重复的组合（顺序不影响）。

示例

• 示例 1：

  • 输入：k = 3, n = 7
  • 输出：[[1,2,4]]

• 示例 2：

  • 输入：k = 3, n = 9
  • 输出：[[1,2,6], [1,3,5], [2,3,4]]

• 示例 3：

  • 输入：k = 4, n = 1
  • 输出：[] （因为最小和为10 > 1）

解题思路

• 回溯算法（Backtracking）：

  • 从数字 1 到 9 中选择数字，构建组合。
  • 每个数字只能使用一次。
  • 同时需要控制组合的长度为 k。

• 剪枝优化：

  • 计算当前组合的长度和总和，提前停止不可能满足条件的路径。
  • 使用递归参数传递当前组合的和和长度，避免全局变量。

关键点

• 限制组合长度：确保每个组合恰好有 k 个数字。
• 固定数字范围：仅使用 1 到 9 的数字。
• 避免重复组合：通过控制递归起始索引，确保组合的唯一性。

示例代码（C++）

#include <vector>
using namespace std;class Solution {
public:vector<vector<int>> res;    // 存储结果vector<int> path;           // 存储当前组合// 回溯函数void backtrack(int k, int n, int startIndex, int currentSum){// 如果当前组合的长度为kif(path.size() == k){if(currentSum == n){res.emplace_back(path);}return;}// 从startIndex开始遍历到9for(int i = startIndex; i <= 9; ++i){// 如果当前数字加上已有的和超过n，提前剪枝if(currentSum + i > n){break;}// 选择当前数字path.push_back(i);// 递归调用，选择下一个数字，更新当前和backtrack(k, n, i + 1, currentSum + i);// 回溯，移除当前数字path.pop_back();}}// 主函数vector<vector<int>> combinationSum3(int k, int n) {// 计算最小和和最大和，提前判断是否有解int minSum = k * (k + 1) / 2;int maxSum = 0;for(int i = 9; i > 9 - k; --i){maxSum += i;}if(n < minSum || n > maxSum){return res; // 无解}backtrack(k, n, 1, 0);return res;}
};

---

通用回溯算法模板

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:vector<vector<int>> res;    // 存储所有符合条件的组合vector<int> path;           // 存储当前的组合路径// 回溯函数void backtrack(vector<int>& candidates, int target, int startIndex, int currentSum, bool allowRepeat){// 终止条件：当前和等于目标if(currentSum == target){res.push_back(path);return;}// 如果当前和超过目标，停止继续if(currentSum > target){return;}// 遍历候选数字for(int i = startIndex; i < candidates.size(); ++i){// 如果当前数字和上一个数字相同，且上一个数字未被选择，跳过以避免重复组合if(i > startIndex && candidates[i] == candidates[i-1]){continue;}// 选择当前数字path.push_back(candidates[i]);// 递归调用// 如果允许重复使用，下一次递归的起始索引为i// 否则，起始索引为i+1backtrack(candidates, target, allowRepeat ? i : i + 1, currentSum + candidates[i], allowRepeat);// 回溯，移除最后一个选择的数字path.pop_back();}}// 组合总和 Ivector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 排序，便于剪枝backtrack(candidates, target, 0, 0, true); // allowRepeat = truereturn res;}// 组合总和 IIvector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 排序，便于处理重复backtrack(candidates, target, 0, 0, false); // allowRepeat = falsereturn res;}// 组合总和 IIIvector<vector<int>> combinationSum3(int k, int n) {res.clear();path.clear();// 数字范围固定为1到9vector<int> candidates;for(int i = 1; i <= 9; ++i){candidates.push_back(i);}// 计算最小和和最大和，提前判断是否有解int minSum = k * (k + 1) / 2;int maxSum = 0;for(int i = 9; i > 9 - k; --i){maxSum += i;}if(n < minSum || n > maxSum){return res; // 无解}backtrack(candidates, n, 0, 0, false); // allowRepeat = false// 过滤出恰好长度为k的组合vector<vector<int>> finalRes;for(auto &comb : res){if(comb.size() == k){finalRes.push_back(comb);}}return finalRes;}
};

模板说明

• 成员变量：

  • res：用于存储所有符合条件的组合结果。
  • path：用于存储当前的组合路径。

• 回溯函数 backtrack：

  • 参数：

    • candidates：候选数字集合。
    • target：目标和。
    • startIndex：当前选择数字的起始索引。
    • currentSum：当前组合的总和。
    • allowRepeat：是否允许重复使用数字（true 表示允许，false 表示不允许）。

  • 逻辑流程：

    1. 终止条件：
       • 如果 currentSum 等于 target，将当前 path 添加到 res 中。
       • 如果 currentSum 超过 target，停止当前路径的递归。
    2. 遍历候选数字：
       • 遍历从 startIndex 开始的所有候选数字。
       • 跳过重复：如果当前数字与前一个数字相同，且前一个数字未被选择，则跳过当前数字以避免重复组合。
    3. 选择数字并递归：
       • 将当前数字加入 path。
       • 递归调用 backtrack：
         • 如果允许重复使用，下一次递归的 startIndex 为 i。
         • 否则，startIndex 为 i + 1。
       • 回溯，移除最后一个选择的数字。

• 具体问题的实现：

  • 组合总和 I：调用 backtrack 时设置 allowRepeat = true。
  • 组合总和 II：调用 backtrack 时设置 allowRepeat = false。
  • 组合总和 III：
    • 生成固定的候选数字集合（1到9）。
    • 在回溯后，过滤出恰好长度为 k 的组合。

使用模板的步骤

1. 准备候选数字集合：

   • 对于组合总和 I 和 II，直接使用输入的 candidates。
   • 对于组合总和 III，生成1到9的数字集合。

2. 排序：

   • 对 candidates 进行排序，以便后续跳过重复数字和剪枝。

3. 调用回溯函数：

   • 根据问题类型，设置 allowRepeat 参数。
   • 对于组合总和 III，可能需要额外的过滤步骤。

4. 处理结果：

   • 返回 res 中存储的所有符合条件的组合。

---

总结对比

特性	组合总和 I	组合总和 II	组合总和 III
数字使用次数	每个数字可以无限次使用	每个数字只能使用一次	每个数字只能使用一次，且恰好有 k 个数字
数字范围	任意给定的正整数集合 candidates	任意给定的正整数集合 candidates（可能有重复）	固定为 1 到 9
重复组合	不允许重复组合（通过排序和控制索引）	不允许重复组合（需跳过重复数字）	不允许重复组合
问题特点	典型的无重复组合问题，允许重复选择数字	包含重复数字的组合问题，每个数字使用一次	特殊限制条件的组合问题，数字固定且数量固定

题目链接

• LeetCode 题目：
  • Combination Sum I
  • Combination Sum II
  • Combination Sum III