Untitled

from typing import Set, List


def get_subset(arr: List[int]) -> Set[int]:
    # gets all possible 2 ** n sums
    # in a naive way with the complexity
    # (2 ** n) * n
    subset = set()
    if not arr:
        return subset
    n = len(arr)
    for i in range(2 ** n):
        cursum = 0
        for j in range(len(arr)):
            if (1 << j) & i:
                cursum += arr[j]
            else:
                cursum -= arr[j]
        subset.add(cursum)
    return subset


def solve_naive(arr: List[int], k: int) -> bool:
    possible_sums = get_subset(arr)
    return k in possible_sums

def solve_fast(arr: List[int], k: int) -> bool:
    n = len(arr)
    set1 = get_subset(arr[:n // 2])
    set2 = get_subset(arr[n // 2:])
    for el in set1:
        if k - el in set2:
            return True
    return False


if __name__ == "__main__":
    assert solve_fast([], 4) == False
    assert solve_fast([1, 2, 3, 4], 0) == True
    assert solve_fast([1, 2, 3, 4], 2) == True
    assert solve_fast([1, 2, 3], 2) == True