一、问题本质与形式化定义
1.1 题目形式化描述
- 输入：无重复整数数组
candidates、目标值target - 输出：所有和为
target的组合集合，满足：- 元素可重复使用
- 组合内元素非降序（避免重复解）
- 解集无重复组合
1.2 问题本质分析
属于无界组合问题（元素可重复选），与0-1组合问题的核心区别在于：
- 0-1组合：每个元素只能选0或1次（对应背包问题中的0-1背包）
- 无界组合：每个元素可选0到多次（对应完全背包问题）
二、回溯法核心实现与状态机模型
2.1 回溯算法的标准框架
void backtracking(参数) {if (终止条件) {处理结果;return;}for (选择：本层可选择的所有选项) {做出选择;backtracking(下一层参数);撤销选择;}
}
本问题中对应的关键映射：
- 选择：将
candidates[i]加入当前组合 - 终止条件：
sum == target或sum > target - 下一层参数：
start=i（允许重复选当前元素）
2.2 状态空间树可视化
以candidates=[2,3,6,7], target=7为例，状态树结构：
根(0)/ | \2 3 6(剪枝) 7/ | \ |2 3 6(剪) 3/ | |
2 3(7) 6(剪)
- 树的深度：最大为
target/最小元素（本例中为7/2=3层） - 分支数：每层最多为
candidates.length - start
三、代码逐行解析与关键技术点
3.1 初始化与排序处理
Arrays.sort(candidates); // 核心优化点
排序的三大作用：
- 剪枝基础：确保后续元素递增，可通过
sum + candidates[i] > target提前终止 - 去重保证：固定组合内元素顺序（如[2,3]不会出现[3,2]）
- 逻辑简化：使递归过程中的选择具有有序性
3.2 回溯函数深度解析
void backtracking(int[] candidates, int target, int start, int sum) {// 终止条件1：找到合法组合if (sum == target) {res.add(new ArrayList<>(temp)); // 注意深拷贝return;}// 终止条件2：超过目标和（剪枝点1）if (sum > target) {return;}// 本层选择遍历（从start开始）for (int i = start; i < candidates.length; i++) {// 剪枝点2：当前选择必超目标和，后续更大元素直接跳过if (sum + candidates[i] > target) break;// 状态变更：选择当前元素sum += candidates[i];temp.add(candidates[i]);// 递归：允许重复选当前元素（i不变）backtracking(candidates, target, i, sum);// 状态回溯：撤销选择sum -= candidates[i];temp.removeLast();}
}
3.2.1 深拷贝的必要性
- 为什么不能直接
res.add(temp)？temp是引用类型，后续回溯会修改其内容- 示例：当找到[2,2,3]后，
temp会被回溯清空，若不拷贝则结果集存储的是空列表
3.2.2 start参数的核心作用
- 控制组合唯一性的关键：
- 当
start=i时，同一层不会重复选前面的元素 - 例如：第一层选2后，第二层只能从i=0（即2）开始选，保证组合内元素非降序
- 当
四、剪枝策略的数学证明与效率分析
4.1 剪枝点的数学推导
定理：若数组已排序，当sum + candidates[i] > target时，后续元素candidates[j] (j>i)必然满足sum + candidates[j] > target
- 证明：
- 因数组排序，故
candidates[j] >= candidates[i] - 则
sum + candidates[j] >= sum + candidates[i] > target
- 因数组排序，故
- 推论：此时可直接
break退出循环，避免无效递归
4.2 时间复杂度精确分析
- 最坏情况（所有元素为1，
target=n）：- 组合数为C(n-1,0)+C(n-1,1)+…+C(n-1,n-1)=2^(n-1)
- 每层递归时间复杂度为O(1)（不考虑深拷贝）
- 总时间复杂度：O(2^target)
- 优化后时间复杂度：
- 设数组最小元素为m，则递归深度最大为target/m
- 实际复杂度：O(k * 2^(target/m))，k为平均分支因子
五、边界情况与扩展问题
5.1 特殊输入处理
- 当
candidates为空或所有元素都大于target时：- 直接返回空列表，无需递归
- 当
target=0时：- 需特殊处理空组合是否合法（本题中target≥1）
5.2 扩展问题：含重复元素的组合总和
若candidates含重复元素（如[1,1,2]），需增加去重逻辑：
for (int i = start; i < candidates.length; i++) {// 同一层中跳过相同元素（去重核心）if (i > start && candidates[i] == candidates[i-1]) continue;// 后续逻辑不变
}
原理：保证同一层中相同元素只处理一次，避免[1,2]和[1,2]这样的重复组合
六、算法执行过程动态演示
6.1 示例输入完整流程
以candidates=[2,3,6,7], target=7为例，递归调用栈变化：
- 初始调用：
backtracking([2,3,6,7],7,0,0) - i=0（元素2）：
- sum=0+2=2 ≤7，加入temp→[2]
- 递归调用：
backtracking([...],7,0,2)
- 第二层i=0：
- sum=2+2=4 ≤7，加入temp→[2,2]
- 递归调用：
backtracking([...],7,0,4)
- 第三层i=0：
- sum=4+2=6 ≤7，加入temp→[2,2,2]
- 递归调用：
backtracking([...],7,0,6)
- 第四层i=0：
- sum=6+2=8 >7，回溯→sum=6，temp→[2,2,2]
- i=1（元素3）：sum=6+3=9>7，回溯
- i=2（元素6）：sum=6+6=12>7，回溯
- i=3（元素7）：sum=6+7=13>7，回溯
- 回到第三层，sum=4，temp→[2,2]
- 第三层i=1（元素3）：
- sum=4+3=7=target，记录组合[2,2,3]
- 回溯→sum=4，temp→[2,2]
- 后续i=2、3均超7，回到第二层
- 第二层i=1（元素3）：
- sum=2+3=5 ≤7，加入temp→[2,3]
- 递归调用：
backtracking([...],7,1,5) - 后续选择3时sum=5+3=8>7，回溯
- 选择6、7均超，回到第一层
- 第一层i=1（元素3）：
- sum=0+3=3 ≤7，加入temp→[3]
- 递归调用中选择3+3+3=9>7，最终无合法组合
- 第一层i=3（元素7）：
- sum=0+7=7=target，记录组合[7]
七、同类问题拓展与解题模板
7.1 组合问题通用解题模板
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void backtrack(int[] nums, int target, int start) {if (target == 0) {res.add(new ArrayList<>(path));return;}if (target < 0) return;for (int i = start; i < nums.length; i++) {// 剪枝条件（根据题目调整）if (nums[i] > target) break;path.add(nums[i]);backtrack(nums, target - nums[i], i); // 可重复选：i不变// backtrack(nums, target - nums[i], i+1); // 不可重复选：i+1path.remove(path.size() - 1);}
}
7.2 相关LeetCode题目拓展
- 39.组合总和（本题，元素可重复）
- 40.组合总和II（元素不可重复，含重复元素）
- 216.组合总和III（选k个不同数字）
- 377.组合总和IV（组合顺序不同算不同解）
八、常见误区与调试技巧
8.1 典型错误分析
-
重复组合问题：
- 错误原因：未控制
start参数，导致[2,3]和[3,2]同时出现 - 解决方案：确保递归时传递
i而非i+1，并通过排序固定顺序
- 错误原因：未控制
-
深拷贝遗漏：
- 错误现象：结果集所有组合最终都为空
- 原因：直接存储
temp引用，后续回溯修改了其内容
8.2 调试技巧
- 打印递归轨迹：
System.out.println("当前组合：" + temp + ", 和：" + sum + ", 起始位置：" + start); - 可视化状态树：
- 使用递归深度和当前选择绘制树状图
- 标记剪枝发生的节点位置
九、总结：回溯法解决组合问题的核心要素
-
状态定义：
- 用
path记录当前组合，sum记录当前和 - 用
start参数控制组合唯一性
- 用
-
递归设计：
- 终止条件：和为target或超过target
- 选择逻辑：当前层可选择的元素范围
-
优化策略：
- 排序+剪枝减少搜索空间
- 深拷贝避免结果污染
掌握这三个核心要素，即可高效解决各类组合搜索问题，从基础的组合总和到复杂的排列组合问题均能迎刃而解。
