You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. To partition nums, put each element of nums into one of the two arrays.

Return the minimum possible absolute difference.

&nbsp;
Example 1:

Input: nums = [3,9,7,3]
Output: 2
Explanation: One optimal partition is: [3,9] and [7,3].
The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.


Example 2:

Input: nums = [-36,36]
Output: 72
Explanation: One optimal partition is: [-36] and [36].
The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.


Example 3:

Input: nums = [2,-1,0,4,-2,-9]
Output: 0
Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2].
The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 15
	nums.length == 2 * n
	-107 &lt;= nums[i] &lt;= 107


class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums)//2
        left, right = nums[:n], nums[n:]
        lsum, rsum = sum(left), sum(right)
        
        ans = inf
        for i in range(n+1): 
            vals = sorted(2*sum(combo)-lsum for combo in combinations(left, i))
            for combo in combinations(right, n-i): 
                diff = 2*sum(combo) - rsum
                k = bisect_left(vals, -diff)
                if k: ans = min(ans, abs(vals[k-1] + diff))
                if k < len(vals): ans = min(ans, abs(vals[k] + diff))
        return ans 
class Solution {
    public int minimumDifference(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }

        TreeSet<Integer>[] sets = new TreeSet[n/2+1];
        for (int i = 0; i < (1 << (n / 2)); ++i) {
            int curSum = 0;
            int m = 0;
            for (int j = 0; j < n / 2; ++j) {
                if ((i & (1<<j)) != 0) {
                    curSum += nums[j];
                    m ++;
                }
            }
            if (sets[m] == null)
                sets[m] = new TreeSet<Integer>();
            sets[m].add(curSum);
        }

        int res = Integer.MAX_VALUE / 3;
        for (int i = 0; i < (1 << (n / 2)); ++i) {
            int curSum = 0;
            int m = 0;
            for (int j = 0; j < n / 2; ++j) {
                if ((i & (1<<j)) != 0) {
                    curSum += nums[n/2 + j];
                    m ++;
                }
            }
            int target = (sum - 2 * curSum) / 2;

            Integer left = sets[n/2-m].floor(target), right = sets[n/2-m].ceiling(target);
            if (left != null) {
                res = Math.min(res, Math.abs(sum - 2 * (curSum + left.intValue())));
            }

            if (right != null) {
                res = Math.min(res, Math.abs(sum - 2 * (curSum + right.intValue())));
            }

            if (res == 0)
                return 0;

        }

        return res;
    }
}
// Time Complexity: O(2^(n/2) * n/2 * n/2)
class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size()/2; 
        vector<int> left(nums.begin(), nums.begin()+n), right(nums.begin()+n, nums.begin()+2*n); 
        
        vector<vector<int>> vals(n+1); 
        for (int mask = 0; mask < (1<<n); ++mask) {
            int diff = 0, key = __builtin_popcount(mask); 
            for (int i = 0; i < n; ++i) 
                diff += (mask & (1 << i)) ? left[i] : -left[i]; 
            vals[key].push_back(diff); 
        }
        
        for (auto& v : vals) sort(v.begin(), v.end()); 
        
        int ans = INT_MAX; 
        for (int mask = 0; mask < (1<<n); ++mask) {
            int diff = 0, key = n - __builtin_popcount(mask); 
            for (int i = 0; i < n; ++i) 
                diff += (mask & (1 << i)) ? right[i] : -right[i]; 
            auto it = lower_bound(vals[key].begin(), vals[key].end(), -diff); 
            if (it != vals[key].begin()) ans = min(ans, abs(diff + *prev(it))); 
            if (it != vals[key].end()) ans = min(ans, abs(diff + *it)); 
        }
        return ans; 
    }
};
var minimumDifference = function(nums) {
    let mid = Math.floor(nums.length / 2);
    let firstHalf = nums.slice(0, mid), secondHalf = nums.slice(mid);
    let firstHalfSum = firstHalf.reduce((a, c) => a + c);
    let secondHalfSum = secondHalf.reduce((a, c) => a + c);
    
    // Find all combinations of sums of subsets made up of k integers
    function sumK(arr, set, idx, sum, k) {
        if (k === 0) return set.add(sum);
        if (idx === arr.length) return;
        sumK(arr, set, idx + 1, sum, k);
        sumK(arr, set, idx + 1, sum + arr[idx], k - 1);
    }
    
    function populateArray(dp, arr, isFirstArray) {
        for (let i = 1; i <= arr.length; i++) {
            let set = new Set();
            sumK(arr, set, 0, 0, i);
            set = [...set.values()];
            if (!isFirstArray) {
                // Sort the secondDP array for binary searching
                set.sort((a, b) => a - b);
            }
            // i === a subset of i integers
            dp[i] = (set);
        }
    }

    let firstDP = [[0]], secondDP = [[0]];
    populateArray(firstDP, firstHalf, true);
    populateArray(secondDP, secondHalf, false);
    
    let min = Infinity;
    // i === subset of length i
    for (let i = 1; i < firstDP.length; i++) {
        for (let num1 of firstDP[i]) {
            let remainingNum1 = firstHalfSum - num1;
            
            // i + remainingSubsetLen must equal length n since our goal is to create two arrays of length n
            let remainingSubsetLen = secondHalf.length - i;
            
            let l = 0, r = secondDP[remainingSubsetLen].length - 1;
            while (l <= r) {
                let mid = l + Math.floor((r - l) / 2);
                let num2 = secondDP[remainingSubsetLen][mid];
                let remainingNum2 = secondHalfSum - num2;
				// arr1Sum === sum of subsets of length n and arr2Sum === sum of subsets of length n
				// thereby creating two arrays of length n
                let arr1Sum = num1 + num2, arr2Sum = remainingNum1 + remainingNum2;
                if (arr1Sum === arr2Sum) return 0;

                min = Math.min(min, Math.abs(arr1Sum - arr2Sum));
                if (arr1Sum > arr2Sum) r = mid - 1;
                else l = mid + 1;
            }
        }
    }
    return min;
};
Partition Array Into Two Arrays to Minimize Sum Difference