Partition Array Into Two Arrays to Minimize Sum Difference

'''
PROBLEM: Minimum Difference Between Partition Sums
----------------------------------------------------
Given an array of 2n elements, split them into two groups of exactly n elements each.
Minimize the absolute difference between the sum of the two groups.

    nums = [3, 9, 7, 3]  →  n=2
    Group1 = [3, 9], sum = 12
    Group2 = [7, 3], sum = 10
    Difference = |12 - 10| = 2

INTUITION:
----------
Let total = sum of all elements.
If Group1 has sum S, then Group2 has sum (total - S).
Difference = |S - (total - S)| = |2S - total|

So we want S as close to total/2 as possible.

But we can't just pick any subset — each group must have EXACTLY n elements.
That's the key constraint.

BRUTE FORCE IDEA (Method 1 — commented out):
--------------------------------------------
Split nums into two halves of size n each (left half, right half).
Why split? Because we need to pick exactly n elements total across both halves.
If we pick k elements from the left half, we must pick (n-k) from the right half.

    left  = nums[:n]   → any k elements from here
    right = nums[n:]   → any (n-k) elements from here
    k ranges from 0 to n

Use find_subset_sums_by_size() to get:
    dict1[k] = list of all possible sums using exactly k elements from left half
    dict2[k] = list of all possible sums using exactly k elements from right half

Then for every (k, n-k) split:
    for every left_sum j in dict1[k]:
        for every right_sum r in dict2[n-k]:
            cur_sum = j + r          # this is S (one group's total sum)
            diff = |2*cur_sum - total|
            ans = min(ans, diff)

WHY THIS IS SLOW:
-----------------
For each left sum, we loop over ALL right sums of the matching size.
In the worst case, each dict2[k] has 2^n entries → O(4^n) total.

This is where Method 2 comes in.

find_subset_sums_by_size():
----------------------------
Builds a dictionary where:
    key   = subset size k
    value = list of all possible sums achievable using exactly k elements

Uses DP:
    Start with dp[0] = [0]  (size 0 subset has sum 0)
    For each number, branch: take it (size+1, sum+num) or leave it (unchanged)
    Merge both branches back into dp

    Example: arr = [3, 7]
        Start:      dp = {0: [0]}
        After 3:    dp = {0: [0], 1: [3]}
        After 7:    dp = {0: [0], 1: [3, 7], 2: [10]}

METHOD 2 — Binary Search Optimization:
---------------------------------------
The bottleneck in M1 is: for each left_sum j, we scan ALL right sums.
Instead, for a fixed j, we want the right_sum r such that j + r ≈ total/2.
    → r ≈ total/2 - j  (call this "target")

If we SORT dict2[k] for each k, we can binary search for target in O(log(2^n)) = O(n).

Total complexity drops from O(4^n) to O(2^n * n).

WHY bisect_left AND NOT bisect_right:
--------------------------------------
bisect_left(arr, target) returns the index where target would be inserted
to keep arr sorted — specifically the LEFTMOST position.
This means arr[idx] >= target (first element >= target).

We want the closest value to target. The closest can be either:
    - arr[idx]   : first value >= target (just at or above target)
    - arr[idx-1] : last value  <  target (just below target)

So we check BOTH neighbors: idx and idx-1.

Why NOT idx+1?
    arr[idx] is already the first value >= target.
    arr[idx+1] is farther from target than arr[idx] (it's even larger).
    So idx+1 can never be closer than idx — no need to check it.

    Example: dict2[right] = [2, 5, 8, 11], target = 7
        bisect_left → idx = 2  (arr[2] = 8, first value >= 7)
        Check idx   → 8  (above target, distance = 1)
        Check idx-1 → 5  (below target, distance = 2)
        Best = 8  ✓
        idx+1 = 11 → distance = 4, clearly worse, skip.

WHY CHECK BOTH idx AND idx-1:
------------------------------
Target may land between two values. The minimum distance could be on either side.

    dict2[right] = [2, 5, 8, 11], target = 6
        idx = 2  → arr[2] = 8  (distance 2)
        idx-1    → arr[1] = 5  (distance 1)  ← this is better

    dict2[right] = [2, 5, 8, 11], target = 7
        idx = 2  → arr[2] = 8  (distance 1)  ← this is better
        idx-1    → arr[1] = 5  (distance 2)

So neither side is always better — we must check both.

BOUNDARY GUARDS:
----------------
    if idx < len(dict2[right]):   → idx might be == len (target larger than all elements)
    if idx - 1 >= 0:              → idx might be 0 (target smaller than all elements)

CODE WALKTHROUGH (Method 2):
-----------------------------
1. Split nums into two halves of size n.
2. Build dict1 and dict2 using find_subset_sums_by_size().
3. Sort each dict2[k] (enables binary search).
4. For each left size k and each left sum j:
       right = n - k              → must pick this many from right half
       target = total//2 - j      → ideal right sum to make total/2
       idx = bisect_left(dict2[right], target)
       Check idx and idx-1, update ans with |2*(j + right_sum) - total|
5. Return ans.
'''

from collections import defaultdict
import math

def find_subset_sums_by_size(arr): #This will give you a dict whose key will be the size of the subset and values will be all the sums of k size subsets.
    dp = defaultdict(list)
    dp[0] = [0]   # size 0 → sum 0

    for num in arr:
        new_dp = defaultdict(list)
        for size, sums in dp.items():
            for s in sums:
                # take current element → size increases by 1
                new_dp[size + 1].append(s + num)

        # merge new results into dp
        for size, sums in new_dp.items():
            dp[size].extend(sums)

    return dp
#M-1
# class Solution:
#     def minimumDifference(self, nums: List[int]) -> int:
#         #first divide it into two and find all the subsets sums of those tow
#         n=len(nums)
#         n//=2
#         dict1=find_subset_sums_by_size(nums[:n])
#         dict2=find_subset_sums_by_size(nums[n:])
#         total=sum(nums)
#         ans=math.inf
#         #sum1
#         #sum2=total-sum1
#         print(dict1)
#         print(dict2)
#         for k,v in dict1.items():
#             for j in v: #left size set=k #right size set=n-k where n is half of the array because in one set, we have to take n//2 elements only
#                 right=n-k
#                 print("The right value is ",right)
#                 for r in dict2[right]:
#                     cur_sum=j+r
#                     ans=min(ans,abs(2*cur_sum-total))
#                     print(f"left size: {k}, right_size: {right}, left_sum: {cur_sum}, difference: {2*cur_sum-total}")
#         return ans
from bisect import bisect_left
class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n=len(nums)
        n//=2
        dict1=find_subset_sums_by_size(nums[:n])
        dict2=find_subset_sums_by_size(nums[n:])
        total=sum(nums)
        ans=math.inf

        for k,v in dict2.items(): #it is sorted now, so that we can apply the binary search on it
            dict2[k].sort()

        for k,v in dict1.items():
            for j in v:
                right=n-k #we need this many elements from the right side
                target=total//2-j #j is the sum from left side
                idx=bisect_left(dict2[right],target)

                #here there are two possibilities, either on left or right
                if idx<len(dict2[right]):
                    cur_sum=dict2[right][idx]+j
                    ans=min(ans, abs(2*cur_sum-total))
                if idx-1>=0:
                    cur_sum=dict2[right][idx-1]+j
                    ans=min(ans, abs(2*cur_sum-total))

        return ans