回溯中等1 种解法
#39组合总和
从互不相同的正整数中可重复选数，找出总和等于 target 的所有组合。
#回溯#数组#剪枝
原题
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
解题主线
- 递归仍从当前下标 i 开始，表示当前数字可以重复使用。
- 排序后路径天然非递减，既避免排列型重复，也能在候选值大于剩余值时直接结束循环。
解法 1：排序 + 可重复选择回溯
复制并排序 candidates，以 remaining 表示尚需凑出的和；选择 nums[i] 后仍从 i 递归。
-
时间复杂度： O(n log n + n^(target/min))，min 为最小候选值，后半项是搜索树上界
-
空间复杂度： O(target/min)，不计输出和排序副本
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int[] numbers = candidates.clone();
Arrays.sort(numbers);
List<List<Integer>> result = new ArrayList<>();
backtrack(numbers, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] numbers, int remaining, int start,
List<Integer> path, List<List<Integer>> result) {
// remaining 为当前路径尚需凑出的和，归零时得到一个完整组合
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
// 只从 start 向后选择，使路径非递减并避免排列型重复
for (int i = start; i < numbers.length; i++) {
// 数组已排序，当前值过大时后续候选也全部不可行
if (numbers[i] > remaining) {
break;
}
path.add(numbers[i]);
// 仍从 i 递归，允许同一候选值被重复使用
backtrack(numbers, remaining - numbers[i], i, path, result);
// 撤销本层选择，恢复路径后再尝试下一个候选
path.remove(path.size() - 1);
}
}
}实现提示
- 合并两个同题文件；二者算法相同，仅保留修复撤销错误后的一个版本。
边界与易错点
- 撤销时必须恢复剩余和或路径和；旧实现中把减法误写成加法会使状态持续膨胀。
- 不能每层从 0 开始，否则同一组合会按不同顺序重复出现。
- 结果、路径和累计值不要保存在跨调用复用的实例字段中。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q039_combinationSum.javabacktrack/Q039_traverse_combinationSum.java