给定一个正数数组arr，请把arr中所有的数分成两个集合
如果arr长度为偶数，两个集合包含数的个数要一样多
如果arr长度为奇数，两个集合包含数的个数必须只差一个
请尽量让两个集合的累加和接近
返回最接近的情况下，较小集合的累加和

字节面试

​

暴力递归

	public static int right(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //计算arr数组的累加和
        int sum = 0;
        for (int nub : arr) {
            sum += nub;
        }
        //偶数长度
        if (arr.length % 2 == 0) {
            return process(arr, 0, arr.length / 2, sum / 2);
        } else { //奇数长度
            //注意此处应该取最大值。
            return Math.max(process(arr, 0, arr.length / 2, sum / 2), process(arr, 0, arr.length / 2 + 1, sum / 2));
        }

    }

    //从index位置开始向后遍历，找到picks个数字组成的最接近rest但不超过rest的累加和。
    public static int process(int[] arr, int index, int picks, int rest) {
        if (index == arr.length) {
            //如果返回-1的话，这种情况本身就是错误的。
            return picks == 0 ? 0 : -1;
        }
        //还没走到头
        if (picks == 0) {
            return 0;
        }
        //既没走到头，picks又不等于0
        //要当前位置的数。
        int p1 = -1;
        int next = -1;
        next = process(arr, index + 1, picks - 1, rest - arr[index]);

        if (next != -1 && arr[index] <= rest) {
            p1 = arr[index] + next;
        }
        //不要当前位置的数
        int p2 = process(arr, index + 1, picks, rest);

        return Math.max(p1, p2);
    }

dp方法优化

	public static int dp(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //计算arr数组的累加和
        int sum = 0;
        for (int nub : arr) {
            sum += nub;
        }
        //创建一个dp表
        int N = arr.length;
        int M = (N + 1) / 2;//向上取证办法，8 -> 4   9 -> 5
        sum /= 2;
        int[][][] dp = new int[N + 1][M + 1][sum + 1];
        //初始化所有的位置都是-1。
        for (int idnex1 = 0; idnex1 <= N; idnex1++) {
            for (int picks1 = 0; picks1 <= M; picks1++) {
                for (int rest1 = 0; rest1 <= sum; rest1++) {
                    dp[idnex1][picks1][rest1] = -1;
                }
            }
        }
        //初始化base case。
        for (int index1 = 0; index1 <= N; index1++) {
            for (int rest1 = 0; rest1 <= sum; rest1++) {
                dp[index1][0][rest1] = 0;
            }
        }
        //计算剩余位置。
        for (int index1 = N - 1; index1 >= 0; index1--) {
            for (int picks1 = 1; picks1 <= M; picks1++) {
                for (int rest1 = 0; rest1 <= sum; rest1++) {
                    int p1 = -1;
                    int next = -1;
                    if(rest1 - arr[index1] >= 0) {
                        next = dp[index1 + 1][picks1 - 1][rest1 - arr[index1]];
                    }
                    if (next != -1 && arr[index1] <= rest1) {
                        p1 = arr[index1] + next;
                    }
                    //不要当前位置的数
                    int p2 = dp[index1 + 1][picks1][rest1];
                    dp[index1][picks1][rest1] = Math.max(p1, p2);
                }
            }
        }
        //偶数长度
        if (arr.length % 2 == 0) {
            return dp[0][arr.length / 2][sum];
        } else { //奇数长度
            //注意此处应该取最大值。
            return Math.max(dp[0][arr.length / 2][sum], dp[0][arr.length / 2 + 1][sum]);
        }

注意dp优化的时候一定要按照暴力递归中的顺序来，先将基本的base case建设好，然后再向后进行一步一步的建设。