一个java 题目，大神帮帮我~~

Question

给一个任意的集合 随机数字x
取n个数字求和
找到最接近x的数(小于等于)

            如 [2,3,5,10,30]  x=20  n=3
            目标数就是18

Answer 1

其实这个题的本质究竟考察点是什么，这个很重要，楼上qq_16127313的回答有些不得要领。这种类型的面试题如果这样回答，很显然会把面试官噎住。
我们一起分析一下这个问题，这个问题本质上和01背包问题很像，解决01背包问题方式有很多：动态规划和剪枝
动态规划一时间想不出dp推导，所以解决问题算法：深度优先+剪枝，其实这种问题没有什么好的手段，正常的思路就是爆搜，这种时间复杂度是n!，当n等于30的时候代码就废掉了。
不剪枝：

import java.util.HashSet;
import java.util.Set;

/**
 * @author yufei.liu
 */
public class Search {

    /**
     * 带有剪枝的搜素
     *
     * @param array        数组
     * @param searchedSet  当前搜索的集合
     * @param n            搜索的层数
     * @param N            最终结果
     * @param optimum      当前全局最优解
     */
    private static void search(int[] array, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
        int optimumValue = sum(optimum);
        if (searchedSet.size() == n) {
            int sum = sum(searchedSet);
            if (sum <= N && sum > optimumValue) {
                optimum.clear();
                optimum.addAll(searchedSet);
            }
            return;
        }
        for (Integer item : array) {
            if (searchedSet.contains(item)) {
                continue;
            }
            Set<Integer> temp = new HashSet<>(searchedSet);
            temp.add(item);
            search(array, temp, n, N, optimum);
        }
    }

    private static int sum(Set<Integer> set) {
        int sum = 0;
        for (Integer item : set) {
            sum += item;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] array = new int[] {2,3,5,10,30};
        int n = 3;
        int N = 20;
        Set<Integer> set = new HashSet<>();
        Set<Integer> optimum = new HashSet<>();

        search(array, set, n, N, optimum);
        System.out.println(optimum);
    }

}

剪枝：

import java.util.HashSet;
import java.util.Set;

/**
 * @author yufei.liu
 */
public class Search {

    /**
     * 带有剪枝的搜素
     *
     * @param array        数组
     * @param searchedSet  当前搜索的集合
     * @param n            搜索的层数
     * @param N            最终结果
     * @param optimum      当前全局最优解
     */
    private static void search(int[] array, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
        int optimumValue = sum(optimum);
        if (searchedSet.size() == n) {
            int sum = sum(searchedSet);
            if (sum <= N && sum > optimumValue) {
                optimum.clear();
                optimum.addAll(searchedSet);
            }
            return;
        } else {
            // 动态剪枝，如果拿到了10，30，这个时候就没有必要继续搜索了，直接返回
            int currentValue = sum(searchedSet);
            if (currentValue > N) {
                return;
            }
        }
        for (Integer item : array) {
            if (searchedSet.contains(item)) {
                continue;
            }
            Set<Integer> temp = new HashSet<>(searchedSet);
            temp.add(item);
            search(array, temp, n, N, optimum);
        }
    }

    private static int sum(Set<Integer> set) {
        int sum = 0;
        for (Integer item : set) {
            sum += item;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] array = new int[] {2,3,5,10,30};
        int n = 3;
        int N = 20;
        Set<Integer> set = new HashSet<>();
        Set<Integer> optimum = new HashSet<>();

        search(array, set, n, N, optimum);
        System.out.println(optimum);
    }

}

上面剪枝剪的不够彻底：
1. 如果数组中最小值是2，那么只要currentvalue > N - 2，这种情况下同样没必要搜索了
2. 如果当前最优解是18，currentvalue + arrayMax <= 18，这种情况下没必要继续搜索
所以最终的代码：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author yufei.liu
 */
public class Search {

    /**
     * 带有剪枝的搜素
     *
     * @param array        数组
     * @param searchedSet  当前搜索的集合
     * @param n            搜索的层数
     * @param arrayMin     数组最小值
     * @param N            最终结果
     * @param optimum      当前全局最优解
     */
    private static void search(int[] array, int arrayMin, int arrayMax, Set<Integer> searchedSet, int n, int N, Set<Integer> optimum) {
        int optimumValue = sum(optimum);
        if (searchedSet.size() == n) {
            int sum = sum(searchedSet);
            if (sum <= N && sum > optimumValue) {
                optimum.clear();
                optimum.addAll(searchedSet);
            }
            return;
        } else {
            // 动态剪枝，如果拿到了10，30，这个时候就没有必要继续搜索了，直接返回
            int currentValue = sum(searchedSet);
            if (currentValue > N - arrayMin || currentValue + arrayMax <= optimumValue) {
                return;
            }
        }
        for (Integer item : array) {
            if (searchedSet.contains(item)) {
                continue;
            }
            Set<Integer> temp = new HashSet<>(searchedSet);
            temp.add(item);
            search(array, arrayMin, arrayMax, temp, n, N, optimum);
        }
    }

    private static int sum(Set<Integer> set) {
        int sum = 0;
        for (Integer item : set) {
            sum += item;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] array = new int[] {2,3,5,10,30};
        int n = 3;
        int N = 20;
        Set<Integer> set = new HashSet<>();
        Set<Integer> optimum = new HashSet<>();
        int arrayMin = Arrays.stream(array).min().getAsInt();
        int arrayMax = Arrays.stream(array).max().getAsInt();

        search(array, arrayMin, arrayMax, set, n, N, optimum);
        System.out.println(optimum);
    }

}