从一组数字中，找出N个相加最接近一个指定数字的N组数字来 请问用java怎么实现？ 求大佬

Question

从一组数字中，找出N个相加最接近一个指定数字的N组数字来 请问用java怎么实现？ 求大佬

Answer 1

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 基本思路，要求数组中的N个数的和与目标数最接近的情况
 * 枚举出数组中所有N个数的组合情况，比如[1,2,3]，所有结果[1,2],[1,3],[2,3]，然后将和与目标值比较
 * 具体思路是通过递归，从数组的第一位开始，每一位都是可选可不选的情况
 * 当选择的数量达到N个时截止，求此时的和是否最接近目标数
 * （这里通过一个临时变量记录最小的差异已经临时结果，每次迭代最小的差异和结果）
 */
public class Main {
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3, 4, 5};
        target = 9;
        N = 3;
        fun(0, 0, new ArrayList<>());
        System.out.println(result);
    }

    static int[] arr;
    static int minDiff = Integer.MAX_VALUE;
    static int target;
    static int N;
    static Set<List<Integer>> result = new HashSet<>();

    public static void fun(int curIndex, int cnt, List<Integer> temp) {
        int diff = sum(temp) - target;
        // 如果和减去target结果大于当前最小的差异提前结束
        if (diff > minDiff) {
            return;
        }
        // 选出了N个数字，求和减去目标数的绝对值是否小于当前求得的最小差异
        // 如果等于则添加预选结果（结果可能多个）
        // 如果小于则替换最小差异，先清空当前结果列表，并将此结果添加尾预选结果
        if (cnt == N) {
            if (Math.abs(diff) == minDiff) {
                result.add(new ArrayList<>(temp));
            }
            if (Math.abs(diff) < minDiff) {
                result.clear();
                minDiff = Math.abs(diff);
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        // 已经到末尾了
        if (curIndex == arr.length) {
            return;
        }
        temp.add(arr[curIndex]);
        fun(curIndex + 1, cnt + 1, new ArrayList<>(temp));
        temp.remove(cnt);
        fun(curIndex + 1, cnt, new ArrayList<>(temp));
    }

    public static int sum(List<Integer> list) {
        return list.stream().mapToInt(e -> e).sum();
    }
}

运行结果：