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

<p>Return <em>the <strong>minimum</strong> possible absolute difference</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/10/02/ex1.png" style="width: 240px; height: 106px;" />
<pre>
<strong>Input:</strong> nums = [3,9,7,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>
<img alt="example-3" src="https://assets.leetcode.com/uploads/2021/10/02/ex3.png" style="width: 316px; height: 106px;" />
<pre>
<strong>Input:</strong> nums = [2,-1,0,4,-2,-9]
<strong>Output:</strong> 0
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
	<li><code>nums.length == 2 * n</code></li>
	<li><code>-10<sup>7</sup> &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>
</ul>

from typing import List, Dict
from itertools import combinations
from bisect import bisect_left

class Solution:
    
    def nums_to_sums(self, nums: List[int], sorted: bool) -> Dict[int, List[int]]:
        sums = {}
        # iterate through all possible subset lengths
        for k in range(len(nums) + 1):
            sums[k] = []
            # iterate through all subsets of length `k` and get their sum
            for comb in combinations(nums, k):
                sums[k].append(sum(comb))
            if sorted:
                sums[k].sort()
        return sums
    
    def minimumDifference(self, nums: List[int]) -> int:
        # split `nums` into left and right halves
        # and find all sublists of each half: O(2^(n//2))
        n = len(nums)//2
        left_nums, right_nums = nums[:n], nums[n:]
        left_sums, right_sums = self.nums_to_sums(left_nums, False), self.nums_to_sums(right_nums, True)

        # e.g. 
        #   nums = [3,9,5,11]
        #   left_nums = [3,9]
        #   left_sums = {
        #       0: [0],
        #       1: [3,9],
        #       2: [12],
        #   }
        #   right_nums = [5,11]
        #   right_sums = {
        #       0: [0],
        #       1: [5,11],
        #       2: [16],
        #   }
        # We need to choose a total of `n` numbers from the left and right sets to form one partition
        # Once we have chosen one partition, the other is already determined
        # Goal: Partitions sums should be as close as possible

        res = None
        num_sum = sum(nums)
        h_sum = num_sum // 2
        for k in range(n+1):
            # assume we're choosing `k` nums from left list for our partition
            for l_sum in left_sums[k]:
                # we want the best r_sum from the remaining `n-k` nums
                # "best": make l_sum + r_sum as close to h_sum as possible
                remainder = h_sum - l_sum
                # find index of values closest to `remainder`
                r_idx = bisect_left(right_sums[n-k], remainder)
                # check possible values on both sides (if idx not out of range)
                for idx in [r_idx, r_idx - 1]:
                    if 0 <= idx < len(right_sums[n-k]):
                        r_sum = right_sums[n-k][idx]
                        sub_sum = l_sum + r_sum
                        sum_diff = abs(sub_sum - (num_sum - sub_sum))
                        if res is None or sum_diff < res:
                            res = sum_diff
        
        # e.g. (cont. from above)
        #   total sum = 3+9+5+11 = 28
        #   half sum = 14
        #
        #   choose 0 from left -> choose 2 from right
        #       possible sums = left_sums[0] = [0]
        #           0: need closest sum to 14-0=14 from right_sums[2]
        #               right_sums[2] = [16], 16 is closest
        #               sublist sum = 0+16=16, other sum = 28-16=12
        #               difference is |16-12| = 4
        #
        #   choose 1 from left -> choose 1 from right
        #       possible sums = left_sums[1] = [3,9]
        #           3: need closest sum to 14-3=11 from right_sums[1]
        #               right_sums[1] = [5,11], 11 is closest
        #               sublist sum = 3+11 = 14, other sum = 28-14=14
        #               difference is |14-14| = 0
        #           9: need closest sum to 14-9=5 from right_sums[1]
        #               right_sums[1] = [5,11], 5 is closest
        #               sublist sum = 9+5 = 14, other sum = 28-14=14
        #               difference is |14-14| = 0
        #
        #   choose 2 from left -> choose 0 from right
        #       possible sums = left_sums[2] = [12]
        #           12: need closest sum to 14-12=2 from right_sums[0]
        #               right_sums[0] = [0], 0 is closest
        #               sublist sum = 12+0=12, other sum = 28-12=16
        #               difference is |12-16|=4
        #
        # minimum difference we found: 0
        #   in lists [3, 11] and [9, 5]

        return res

solution = Solution()
print(solution.minimumDifference([3,9,5,11]))
19500