문제 설명

정의

부분집합 중 합이 0인 경우의 존재여부를 구하여라

입력

첫 줄에 테스트케이스의 개수가 주어지며 그 다음 줄에 10개의 원소들이 주어진다.

3
19 6 16 19 15 16 8 13 16 10
-20 -6 -13 3 -19 -9 19 -3 9 4
7 7 19 1 -18 5 -9 -11 19 18

출력

부분집합의 합이 0인 경우가 존재할 경우 True를, 0인 경우가 존재하지 않을 경우 False를 출력한다.

#1 False
#2 True
#3 True

문제 풀이

이진탐색을 이용한다.
1. 이진 탐색을 이용해 부분집합의 원소들을 sumArray에 넣는다.
2. sumArray의 원소들의 합을 구하고, 만약 0일 경우 False를 출력한다.

코드

T = int(input())
for tc in range(1, T + 1):
    arr = list(map(int, input().split()))
    for i in range(1 << 10):
        sumArray = []
        for j in range(10):
            if i & (1 << j):
                sumArray.append(arr[j])
        if len(sumArray) > 0 and sum(sumArray) == 0:
            print(f"#{tc} True")
            break
        if i == 1 << 10 - 1:
            print(f"#{tc} False")