<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 sys import maxsize

class Solution:

    def count_set_bits(self, num):
        count = 0
        while num:
            count+=1
            num = num&(num-1)
        return count

    # mem limit exceed
    def minimumDifference_2(self, nums: List[int]) -> int:
        op = maxsize
        nums_len = len(nums)
        nums_sum = sum(nums)
        mid = nums_len//2
        dp_len = 1<<nums_len
        dp = [maxsize for i in range(dp_len)]
        dp[0] = 0
        for i in range(dp_len):
            # print(f'{i=} {dp=}')
            if dp[i] is maxsize: continue
            i_set_bits = self.count_set_bits(i)
            if i_set_bits>=mid: continue # as count of items in set will become >mid
            for j in range(nums_len):
                if i&(1<<j)==0:
                    t_sum = dp[i] + nums[j]
                    dp[i|(1<<j)] = t_sum
                    if (i_set_bits==(mid-1)):
                        op = min(op, abs(nums_sum-(2*t_sum)))
        return op
    
    # retuns a dict with key as number of elements, value is all sum combination that can be made
    # this will timeout. See below for simple and fast solution
    def get_all_sum_combinations_dp(self, nums, nums_len) -> int:
        op = dict()
        dp_len = (1<<nums_len)
        dp = [None for i in range(dp_len)]
        dp[0] = 0
        for i in range(dp_len):
            # print(f'{i=} {dp=}')
            if dp[i] is None: continue
            i_set_bits = self.count_set_bits(i)
            for j in range(nums_len):
                if i&(1<<j)==0:
                    t_sum = dp[i] + nums[j]
                    dp[i|(1<<j)] = t_sum
                    sum_set = op.get(i_set_bits+1, set())
                    sum_set.add(t_sum)
                    op[i_set_bits+1] = sum_set
        return op

    # retuns a list with index as number of elements, value is all sum combination 
    # that can be made with those number of element
    def get_all_sum_combinations(self, nums, nums_len) -> int:
        dp = [list() for i in range(nums_len+1)] 
        for num in nums:
            for i in range(nums_len, 0, -1):
                if i==1:
                    dp[i].append(num)
                elif len(dp[i-1])>0:
                    for t_num in dp[i-1]:
                        dp[i].append(t_num+num)
        return dp
    
    def get_nearest_num_to_target(self, nums, nums_len, k, target):
        _floor = -1
        nums.sort()
        s, e = 0, nums_len-1
        while s<=e:
            mid = s + (e-s)//2
            if (nums[mid]+k)==target: return nums[mid]
            if (nums[mid]+k)<target:
                _floor = mid
                s = mid+1
            else:
                e = mid-1
        # print(f'{s=} {e=} {_floor=}')
        return nums[_floor] if (_floor==e) or ((_floor>-1) and (k-nums[_floor])<=(nums[_floor+1]-k)) else nums[_floor+1]

    def minimumDifference(self, nums: List[int]) -> int:
        op = maxsize
        nums_len = len(nums)
        nums_sum = sum(nums)
        mid = nums_len//2
        mid_sum = nums_sum//2
        arr1_sum_combinations = self.get_all_sum_combinations(nums[:mid], mid)
        arr2_sum_combinations = self.get_all_sum_combinations(nums[mid:], mid)
        # print(f'{arr1_sum_combinations=}')
        # print(f'{arr2_sum_combinations=}')
        # print(f'{nums_sum=} {mid_sum=}')
        for num_count in range(1, mid+1):
            arr1_sum_combination = arr1_sum_combinations[num_count]
            arr2_sum_combination = arr2_sum_combinations[mid-num_count]
            if not arr2_sum_combination: # Case when num_count == mid
                # print(f'{num_count=} {arr1_sum_combination=} {arr2_sum_combination=}')
                for arr1_sum in arr1_sum_combination:
                    op = min(op, abs(nums_sum - 2*arr1_sum))
                    # print(f'{nums_sum=} {2*arr1_sum=} {abs(nums_sum - 2*arr1_sum)=}')
            else:
                arr1_sum_combination.sort()
                arr2_sum_combination.sort()
                arr1_sum_combination_count = len(arr1_sum_combination)
                arr2_sum_combination_count = len(arr2_sum_combination)
                # print(f'{num_count=} {mid=} {arr1_sum_combination=} {arr2_sum_combination=}')
                i, j = 0, arr2_sum_combination_count-1
                while i<arr1_sum_combination_count and j>=0:
                    x, y = arr1_sum_combination[i], arr2_sum_combination[j]
                    z = x+y
                    # print(f'{x=} {y=} {z=} {i=} {j=} {op=}')
                    if z==mid_sum:
                        op = min(op, abs(nums_sum - 2*z))
                        break
                    elif z<mid_sum:
                        i+=1
                        op = min(op, abs(nums_sum - 2*z))
                    else:
                        j-=1
                        op = min(op, abs(nums_sum - 2*z))
                # print(f'{nums_sum=} {arr1_sum+arr2_sum=} {abs(nums_sum - (arr1_sum+arr2_sum))=}')
        return op
749