4.4.4 4.4.4

main.py

"""
문제 : 배열의 두 부분집합의 최소 차이 만들기

배열을 두 부분집합을 만들고 각 부분집합의 합 차이가 최소가 되는 값을 반환하라
예를 들어서 [3, 2, 7, 4, 1]이 주어지면 부분집합의 합 차이가 최소가 되게 하려면,
하나는 [1, 7]이 되고, 다른 하나는 [2, 3, 4]가 되었을 때 각 부분집합의 합은 8과 9가 되어서 차이가 1이 된다.
이때 1을 반환하도록 구현하는 것이다.
"""

import sys
from typing import List

min_diff = sys.maxsize
total = 0


def subset_diff(index: int, nums: List[int], subsum: int):
    global total, min_diff
    if index == len(nums):
        min_diff = min(min_diff, abs(((total - subsum) - subsum)))
        return
    subset_diff(index + 1, nums, subsum + nums[index])
    subset_diff(index + 1, nums, subsum)


if __name__ == '__main__':
    arrays = list(map(int, input().split()))
    total = sum(arrays)
    subset_diff(0, arrays, 0)
    print(min_diff)