<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>

import bisect
import collections
from typing import List


class Solution:
    # brute force O(n2^(2n)) - too slow but works
    def minimumDifference1(self, nums: List[int]) -> int:
        half_cnt = len(nums) // 2
        subset_sum = []

        def backtracking(idx: int, cur_sum: int, use_count: int) -> None:
            if idx == len(nums):
                if use_count == half_cnt:
                    subset_sum.append(cur_sum)
                return

            # use the current element
            backtracking(idx + 1, cur_sum + nums[idx], use_count + 1)
            # not use the current element
            backtracking(idx + 1, cur_sum, use_count)

        backtracking(0, 0, 0)

        min_diff = float("inf")
        nums_sum = sum(nums)
        
        # remove the empty subset and full subset
        empty_subset_encounter = False
        full_subset_encounter = False

        # must take into account the existing of one empty subset and one all subset
        for first_total in subset_sum:
            if first_total == 0 and not empty_subset_encounter:
                empty_subset_encounter = True
                continue
            elif first_total == nums_sum and not full_subset_encounter:
                full_subset_encounter = True
                continue
            
            second_total = nums_sum - first_total
            min_diff = min(min_diff, abs(first_total - second_total))

        return min_diff
    
    
    # slightly better - still O(n2^n)
    # the idea is that we arbitrarily create two n-len list and find all subset sum inside
    # https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/solutions/1513298/c-meet-in-middle/
    def minimumDifference(self, nums: List[int]) -> int:
        HALF = len(nums) // 2
        TOTAL_SUM = sum(nums)
        
        left_arr, right_arr = nums[0:HALF], nums[HALF:len(nums)]
        
        left_subset, right_subset = collections.defaultdict(list), collections.defaultdict(list)
        
        
        def subset_sum(arr: List[int], used_set: dict[int, List[int]], idx: int, num_used: int, cur_sum: int) -> None:
            if idx == len(arr):
                used_set[num_used].append(cur_sum)
                return
            
            # use the current index
            subset_sum(arr, used_set, idx + 1, num_used + 1, cur_sum + arr[idx])
            # not use the current index
            subset_sum(arr, used_set, idx + 1, num_used, cur_sum)
            
        subset_sum(left_arr, left_subset, 0, 0, 0)
        subset_sum(right_arr, right_subset, 0, 0, 0)
        
        
        
        
        
        result = abs(sum(left_arr) - sum(right_arr))
        
        for left_used in range(1, HALF):
            right_used = HALF - left_used
            
            right_subset[right_used].sort()
            
            for left_sum in left_subset[left_used]:
                target_sum = TOTAL_SUM//2 - left_sum
                search_start = bisect.bisect_left(right_subset[right_used], target_sum)
                
                for i in [search_start, search_start + 1]:
                    if i < len(right_subset[right_used]):
                        first_subset_sum = left_sum + right_subset[right_used][i]
                        second_subset_sum = TOTAL_SUM - first_subset_sum
                        result = min(result, abs(first_subset_sum - second_subset_sum))
                    
        
        return result



sol = Solution()
sol.minimumDifference([3,9,7,3])

2212