39. 组合总和#

// 主函数：返回所有和为 target 的组合
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // result：保存最终所有满足条件的组合
    List<List<Integer>> result = new ArrayList<>();
    // 先排序：便于后续使用 candidates[i] > remain 时直接剪枝
    Arrays.sort(candidates);
    // 启动回溯：
    // - path 初始为空，记录当前组合
    // - remain 初始为 target，表示还需要凑出的和
    // - start 为 0，表示从第 0 个候选数开始尝试
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    // 返回所有合法组合
    return result;
}

// 回溯函数：在当前 path 基础上，继续尝试拼出 remain
private void backtrack(List<List<Integer>> result, List<Integer> path, 
                      int[] candidates, int remain, int start) {
    // 剪枝：如果剩余值小于 0，说明当前路径和已超过 target，直接结束该分支
    if (remain < 0) return;

    // 终止条件：remain == 0 表示当前路径刚好凑出 target
    if (remain == 0) {
        // 加入路径副本，避免后续回溯修改影响结果
        result.add(new ArrayList<>(path));
        // 当前分支完成
        return;
    }

    // 从 start 开始枚举候选数：
    // 使用 start 而不是 0，可避免生成顺序不同但本质相同的重复组合
    for (int i = start; i < candidates.length; i++) {
        // 因为数组已排序，若当前数已大于 remain，后面的数只会更大，直接 break
        if (candidates[i] > remain) break;

        // 做选择：把当前候选数加入路径
        path.add(candidates[i]);

        // 递归下一层：
        // - remain 减去当前选择值
        // - start 传 i（不是 i+1），表示同一个元素可以重复选取
        backtrack(result, path, candidates, remain - candidates[i], i);

        // 撤销选择（回溯）：移除最后加入的元素，尝试下一个候选数
        path.remove(path.size() - 1);
    }
}