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

public class MinimalCombinationSum {

    private static List<Double> bestSolution;
    private static double target;
    private static double minDifference;
    private static final double EPSILON = 1e-10;

    public static List<Double> findBestCombination(Double[] candidates, double targetSum) {
        bestSolution = null;
        target = targetSum;
        minDifference = Double.MAX_VALUE;
        Arrays.sort(candidates);
        backtrack(candidates, 0, new ArrayList<>(), 0.0);

        // 如果没有精确解，返回最接近的近似解
        return bestSolution != null ? bestSolution : new ArrayList<>();
    }

    private static void backtrack(Double[] candidates, int start,
                                  List<Double> current, double currentSum) {
        // 计算当前和与目标的差值
        double difference = Math.abs(currentSum - target);

        // 如果找到更优解（差值更小或差值相同但组合更短）
        if (difference < minDifference - EPSILON ||
                (Math.abs(difference - minDifference) < EPSILON &&
                        (bestSolution == null || current.size() < bestSolution.size()))) {
            minDifference = difference;
            bestSolution = new ArrayList<>(current);
        }

        // 如果已经找到精确解，不需要继续搜索更长的组合
        if (minDifference < EPSILON) {
            return;
        }

        // 遍历候选数字
        for (int i = start; i < candidates.length; i++) {
            double num = candidates[i];

            // 剪枝：如果当前和已经远大于目标值，跳过
            if (currentSum + num > target + minDifference + EPSILON) {
                continue;
            }

            // 跳过重复数字
            if (i > start && Math.abs(candidates[i] - candidates[i - 1]) < EPSILON) {
                continue;
            }

            current.add(num);
            backtrack(candidates, i + 1, current, currentSum + num);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        Double[] candidates1 = {1.5, 2.3, 3.1, 4.7};
        double target1 = 3.8;
        System.out.println("候选数字: " + Arrays.toString(candidates1));
        System.out.println("目标值: " + target1);
        List<Double> result1 = findBestCombination(candidates1, target1);
        printResult(result1, target1);

//        Double[] candidates2 = {0.8, 1.2, 1.7, 2.5};
//        double target2 = 3.9;
//        System.out.println("\n候选数字: " + Arrays.toString(candidates2));
//        System.out.println("目标值: " + target2);
//        List<Double> result2 = findBestCombination(candidates2, target2);
//        printResult(result2, target2);
    }

    private static void printResult(List<Double> result, double target) {
        if (result.isEmpty()) {
            System.out.println("无解");
        } else {
            double sum = result.stream().mapToDouble(Double::doubleValue).sum();
            if (Math.abs(sum - target) < EPSILON) {
                System.out.printf("精确解: %s (和=%.2f)\n", result, sum);
            } else {
                System.out.printf("近似解: %s (和=%.2f, 与目标相差: %.2f)\n",
                        result, sum, sum - target);
            }
        }
    }
}