array_partition.py

'''
Example 1:
Input: [1,2,3,6] 
Output: 6     # {1,2,3} and {6} 

Example 2:
Input: [1,2,3,4,5,6] 
Output: 10    # {2,3,5} and {4,6} 

Example3:
Input: [1,2] 
Output: 0     # Unable to create track
'''

def array_partition(arr):
    # Find the target value
    total = sum(arr)
    target = total // 2
    
    combination1 = []
    combination2 = []
    
    arr.sort(reverse=True)
    
    # Create the first combination
    i = 0
    while i < len(arr) and sum(combination1) < target:
        combination1.append(arr[i])
        
        # if exceeded, remove the last added element
        if sum(combination1) > target:
            del combination1[-1]
            i += 1
        else:
            del arr[i]
            
    # Create the second combination
    # Set the first element
    j = 0
    # Find the combinations
    while j < len(arr) and sum(combination2) < target:
        combination2.append(arr[j])
        
        # if exceeded, remove the last added element
        if sum(combination2) > target:
            del combination2[-1]
            j += 1
        else:
            del arr[j]
    
    if sum(combination1) == sum(combination2):
        return sum(combination1)
    else:
        return 0

test_cases = [
    ([1, 2, 3, 6], 6, "Equal partition: {1,2,3} and {6}"),
    ([1, 2, 3, 4, 5, 6], 10, "Unequal partition: {2,3,5} and {4,6}"),
    ([1, 2], 0, "Too small - cannot partition"),
    ([10, 20, 15, 5, 25], 35, "Multiple valid combinations"),
    ([2, 2, 2, 2], 4, "All same elements"),
    ([1, 1, 1, 1, 1], 2, "Odd count of same elements"),
    ([5], 0, "Single element - cannot partition"),
    ([100, 200], 0, "Two large elements - cannot partition"),
    ([1, 5, 11, 5], 11, "Classic DP test case"),
    ([3, 3, 3, 3, 3, 3], 9, "Six identical elements")
]

# Run tests:
for arr, expected, description in test_cases:
    result = array_partition(arr.copy())
    status = "✓ PASS" if result == expected else "✗ FAIL"
    print(f"{status} | Input: {arr} | Expected: {expected}, Got: {result} | {description}")