Java实现double数组元素和为指定值的所有组合算法求助

问题分析 #

你需要找出数组中所有元素的有序组合（顺序不同视为不同组合），使其和等于指定目标值。原代码的两层循环+while逻辑只能固定重复选取某几个元素，无法覆盖所有可能的排列情况，因此无法得到预期输出。

实现思路 #

采用回溯递归的方式遍历所有可能的组合：

• 每次从数组中选择一个元素，将其加入当前组合，并累加和
• 如果当前和与目标值的误差在可接受范围内（处理浮点数精度问题），则记录该组合
• 如果当前和小于目标值，继续递归选择下一个元素
• 如果当前和超过目标值，终止当前分支的递归

完整代码实现 #

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    private static final double[] a = {1.0, 0.5, 0.25};
    private static final double target = 1.0;
    // 处理浮点数精度的阈值，避免因精度误差导致判断错误
    private static final double EPSILON = 1e-9;

    public static void main(String[] args) {
        List<String> result = new ArrayList<>();
        backtrack(new ArrayList<>(), 0.0, result);
        // 输出所有符合条件的组合
        result.forEach(System.out::println);
    }

    private static void backtrack(List<Double> currentCombination, double currentSum, List<String> result) {
        // 判断当前和是否接近目标值（处理浮点数精度）
        if (Math.abs(currentSum - target) < EPSILON) {
            // 将组合转换为空格分隔的字符串
            StringBuilder sb = new StringBuilder();
            for (double num : currentCombination) {
                sb.append(num).append(" ");
            }
            // 移除最后一个多余的空格
            result.add(sb.toString().trim());
            return;
        }
        // 如果当前和已经超过目标值，直接返回
        if (currentSum > target + EPSILON) {
            return;
        }
        // 遍历数组中的每个元素，继续递归
        for (double num : a) {
            currentCombination.add(num);
            backtrack(currentCombination, currentSum + num, result);
            // 回溯：移除最后添加的元素，尝试下一个可能
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

代码说明 #

1. 精度处理：使用EPSILON（1e-9）判断当前和与目标值的差值，避免浮点数运算的精度误差导致正确组合被遗漏。
2. 回溯逻辑：每次递归选择一个元素加入当前组合，递归结束后移除该元素，确保能遍历所有可能的排列组合。
3. 结果收集：当当前和符合目标值时，将组合转换为字符串存入结果列表，最后统一输出。

运行这段代码后，会输出你预期的所有组合：

1.0
0.5 0.5
0.5 0.25 0.25
0.25 0.25 0.25 0.25
0.25 0.25 0.5
0.25 0.5 0.25

内容的提问来源于stack exchange，提问作者thenicknameless