# 2035. Partition Array Into Two Arrays to Minimize Sum Difference
###### tags: `Leetcode` `Hard` `Backtracking` `Bit Manipulation`
## 思路
发现n=15说明可能只能采用指数级别的暴力搜索
但是由于array的size可以到30说明我们不能对整个array暴力搜索
因此我们想办法把array平均分成两部分
前一部分取```i```个值 和为```x``` 那么后一部分我们就取```n-i```个值 和越接近```sum/2-x```越好
于是我们想到我们可以先对后半部分进行预处理 算出取```[0:n]```个值所有得到的结果
接着可以对前半部分用backtracking找出所有可能的值 然后binary search在后半部分找出最接近的
## Code

class Solution {
    public int minimumDifference(int[] nums) {
        int sum = 0;
        for(int num:nums) sum += num;
        int n = nums.length/2;
        List<List<Integer>> secondHalf = new ArrayList<>();
        for(int i=0; i<=n; i++) secondHalf.add(new ArrayList<>());
        secondHalf.get(0).add(0);
        for(int i=n; i<2*n; i++){
            for(int j=n; j>=1; j--){
                // the new element in secondHalf.get(j)==all the old element in secondHalf.get(j-1)+nums[i]
                if(j==1){
                    secondHalf.get(j).add(nums[i]);
                }
                else if(secondHalf.get(j-1).size()==0) continue;
                else{
                    for(int num:secondHalf.get(j-1)) secondHalf.get(j).add(num+nums[i]);
                }
            }
        }
        for(int i=0; i<n; i++){
            Collections.sort(secondHalf.get(i));
        }
        int minDiff = Integer.MAX_VALUE;
        //backtracking to take i elements from the first half and calculate its sum x
        //binary search in the secondHalf.get(n-i) to find the sum closest to totalsum/2-x
        List<List<Integer>> firstHalf = new ArrayList<>();
        for(int i=0; i<=n; i++) firstHalf.add(new ArrayList<>());
        for(int i=0; i<(1<<n); i++){
            getSum(firstHalf, nums, i);
        }
        for(int i=0; i<=n; i++){
            for(int j=0; j<firstHalf.get(i).size(); j++){
                int firstSum = firstHalf.get(i).get(j);
                int secondSum = binarySearch(sum/2-firstSum, secondHalf.get(n-i));
                minDiff = Math.min(minDiff, Math.abs(2*(firstSum+secondSum)-sum));
            }
        }
        return minDiff;
    }
    private int binarySearch(int target, List<Integer> nums){
        int start = 1, end = nums.size();
        while(start<end){
            int mid = start+(end-start)/2;
            if(nums.get(mid)<target){
                start = mid+1;
            }
            else end = mid;
        }
        if(start!=nums.size() && Math.abs(nums.get(start)-target)<Math.abs(nums.get(start-1)-target)) return nums.get(start);
        else return nums.get(start-1);
    }
    private void getSum(List<List<Integer>> firstHalf, int[] nums, int state){
        int res = 0;
        int n = nums.length/2;
        int cnt = 0;
        for(int i=0; i<n; i++){
            if(((state>>i)&1)==1){
                cnt++;
                res += nums[i];
            }
        }
        firstHalf.get(cnt).add(res);
    }
}