回溯中等1 种解法

#39组合总和

从互不相同的正整数中可重复选数，找出总和等于 target 的所有组合。

#回溯#数组#剪枝

解题主线

递归仍从当前下标 i 开始，表示当前数字可以重复使用。

排序后路径天然非递减，既避免排列型重复，也能在候选值大于剩余值时直接结束循环。

解法 1：排序 + 可重复选择回溯

复制并排序 candidates，以 remaining 表示尚需凑出的和；选择 nums[i] 后仍从 i 递归。

时间复杂度

O(n log n + n^(target/min))，min 为最小候选值，后半项是搜索树上界

空间复杂度

O(target/min)，不计输出和排序副本

39. 组合总和 · 排序 + 可重复选择回溯

java

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) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < numbers.length; i++) {
            if (numbers[i] > remaining) {
                break;
            }
            path.add(numbers[i]);
            backtrack(numbers, remaining - numbers[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }
}

复制并排序 candidates，以 remaining 表示尚需凑出的和；选择 nums[i] 后仍从 i 递归。

合并两个同题文件；二者算法相同，仅保留修复撤销错误后的一个版本。

边界与易错点

撤销时必须恢复剩余和或路径和；旧实现中把减法误写成加法会使状态持续膨胀。
不能每层从 0 开始，否则同一组合会按不同顺序重复出现。
结果、路径和累计值不要保存在跨调用复用的实例字段中。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q039_combinationSum.javabacktrack/Q039_traverse_combinationSum.java