2035. Divide the array into two arrays and minimize the difference between the sum of the arrays

Give you a length of  2 * n  Array of integers for . You need to  nums  Divide into   Two   The length is  n  Array of , Find the sum of the two arrays , and   To minimize the   Sum of two arrays   The absolute value of the difference  .nums  Each element in the array needs to be placed in one of two arrays .

Please return   Minimum   The difference between the sum of arrays .

Example 1：

​

 Input ：nums = [3,9,7,3]
 Output ：2
 explain ： The optimal grouping scheme is divided into  [3,9]  and  [7,3] .
 The absolute value of the difference between the sum of the array is  abs((3 + 9) - (7 + 3)) = 2 .

Example 2：

 Input ：nums = [-36,36]
 Output ：72
 explain ： The optimal grouping scheme is divided into  [-36]  and  [36] .
 The absolute value of the difference between the sum of the array is  abs((-36) - (36)) = 72 .

Example 3：

​

 Input ：nums = [2,-1,0,4,-2,-9]
 Output ：0
 explain ： The optimal grouping scheme is divided into  [2,4,-9]  and  [-1,0,-2] .
 The absolute value of the difference between the sum of the array is  abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 .

Tips ：

• 1 <= n <= 15
• nums.length == 2 * n
• -10^7 <= nums[i] <= 10^7

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

Failure . This kind of half search is less written , The train of thought is a little vague ： Subtract the average , Concepts like signs , I still have a look at other solutions （ The main direction of halving , The concept of sign ）, Only then did I have an idea

Method ： Half search

1. An array is cut into left and right parts . length 30 Can't enumerate , however 15 It can be enumerated . Enumerate all half elements into two sets , Put in collection A Of is recorded as a positive number , Put in collection B Is written as a negative number , Use binary 1 and 0 identification . Our goal , Let the difference between two arrays , As close as possible to 0.

2. How to ask for dp subset-sum . First, all 0 The situation of , Is to sum and take the opposite number . Then each additional positive number , Add the last addition twice . Why add it twice ？ such as [3], The minus sign at the beginning is -3, If you change it to take a positive sign , Need to become 3,3-(-3)=6, So you have to add it twice .

3. Take after , It becomes two dp , Temporarily called A and B. We put B Classify according to the number of positive signs , And then put in TreeSet in （ This step is continuous , The outer layer can also be used in length n+1 Array substitution of ,TreeSet It can also be replaced by two points later ）

4. We'll take a total of n Number . The first half is known x individual , Take the second half n-x individual . The value obtained in the first half is A[X], We hope the length of the second half is n-x In the number of , Try to get as close as possible -A[X] Value , You can use the properties of ordered sets ,floor,ceiling Look up and down , Get two values , Sum as small as possible , Compare smaller values , Put in the answer .

class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length/2;
        int[] sums1 = getSum(nums,0);
        int[] sums2 = getSum(nums,n);

        // Sort by length ...
        Map<Integer, TreeSet<Integer>> map = new HashMap<>();

        for(int i = 0; i < 1<<n; i++){
            int cnt = Integer.bitCount(i);
            map.putIfAbsent(cnt,new TreeSet<>());
            map.get(cnt).add(-sums2[i]);
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < 1<<n; i++){
            int cnt = Integer.bitCount(i);
            int v = sums1[i];
            TreeSet<Integer> set = map.get(n-cnt);
            Integer a = set.floor(v);
            if(a!=null)ans = Math.min(ans,Math.abs(v-a));
            Integer b = set.ceiling(v);
            if(b!=null) ans = Math.min(ans,Math.abs(v-b));
        }
        return ans;
    }

    private int[] getSum(int[] nums, int move){
        int n = nums.length/2;
        int[] sums1 = new int[1<<n];
        int total = 0;
        for(int i = move; i < n+move; i++){
            total+=nums[i];
        }
        sums1[0] = -total;
        for(int i = 1; i < 1<<n; i++){
            int lastIndex = Integer.bitCount((i&(-i))-1);
            sums1[i] = sums1[i&(i-1)]+nums[lastIndex+move]*2;
        }
        return sums1;
    }
}