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
表示不允许)。
-
逻辑流程:
- 终止条件:
- 如果
currentSum
等于target
,将当前path
添加到res
中。 - 如果
currentSum
超过target
,停止当前路径的递归。
- 如果
- 遍历候选数字:
- 遍历从
startIndex
开始的所有候选数字。 - 跳过重复:如果当前数字与前一个数字相同,且前一个数字未被选择,则跳过当前数字以避免重复组合。
- 遍历从
- 选择数字并递归:
- 将当前数字加入
path
。 - 递归调用
backtrack
:- 如果允许重复使用,下一次递归的
startIndex
为i
。 - 否则,
startIndex
为i + 1
。
- 如果允许重复使用,下一次递归的
- 回溯,移除最后一个选择的数字。
- 将当前数字加入
- 终止条件:
-
-
具体问题的实现:
- 组合总和 I:调用
backtrack
时设置allowRepeat = true
。 - 组合总和 II:调用
backtrack
时设置allowRepeat = false
。 - 组合总和 III:
- 生成固定的候选数字集合(1到9)。
- 在回溯后,过滤出恰好长度为
k
的组合。
- 组合总和 I:调用
使用模板的步骤
-
准备候选数字集合:
- 对于组合总和 I 和 II,直接使用输入的
candidates
。 - 对于组合总和 III,生成1到9的数字集合。
- 对于组合总和 I 和 II,直接使用输入的
-
排序:
- 对
candidates
进行排序,以便后续跳过重复数字和剪枝。
- 对
-
调用回溯函数:
- 根据问题类型,设置
allowRepeat
参数。 - 对于组合总和 III,可能需要额外的过滤步骤。
- 根据问题类型,设置
-
处理结果:
- 返回
res
中存储的所有符合条件的组合。
- 返回
总结对比
特性 | 组合总和 I | 组合总和 II | 组合总和 III |
---|---|---|---|
数字使用次数 | 每个数字可以无限次使用 | 每个数字只能使用一次 | 每个数字只能使用一次,且恰好有 k 个数字 |
数字范围 | 任意给定的正整数集合 candidates | 任意给定的正整数集合 candidates (可能有重复) | 固定为 1 到 9 |
重复组合 | 不允许重复组合(通过排序和控制索引) | 不允许重复组合(需跳过重复数字) | 不允许重复组合 |
问题特点 | 典型的无重复组合问题,允许重复选择数字 | 包含重复数字的组合问题,每个数字使用一次 | 特殊限制条件的组合问题,数字固定且数量固定 |
题目链接
- LeetCode 题目:
- Combination Sum I
- Combination Sum II
- Combination Sum III