Inflearn Community Q&A

강의를 보기전에 짜본 코드인데 어디가 잘못된지를 모르겠어서 질문드립니다.

전체적인 로직은 앞 강의에서 배운 부분집합 로직에서 조금 추가한 것으로

각 부분집합의 합을 구하고 구한 합을 cand_dic이란 딕셔너리의 key값으로 넣고 value는 만약 이미 그 합이 존재하면 1씩 더해서 나중에 cand_dic을 둘러보았을 때 value가 1보다 큰 값이 있다면 부분집합의 합이 겹치는거니까 yes를 출력하게 한 것입니다.

저 그리고 강의에서 sum=total-sum으로 진위여부를 판단하셨는데 문제를 보면 두 개의 부분집합으로 나뉜다고 나와있는데 그럼 예를들어서

{1,3,5,6,7,10}이 있을때 {1,3}  {5,6} 이렇게해도 두 개의 부분집합으로 나뉜거 아닌가요?? 그럼 sum=total-sum으로 판단을 하면 오류가 생기지 않나요?

제가 문제 이해를 잘못한건가요?

def dfs(cnt=1):
    if cnt == n+1:
        cand = 0
        for k, v in set_dic.items():
            if v == 1:
                cand += k
        cand_dic[cand] = cand_dic.get(cand, 0) + 1
    else:
        set_dic[set_list[cnt-1]] = 1
        dfs(cnt+1)
        set_dic[set_list[cnt-1]] = 0
        dfs(cnt+1)




n = int(input())
set_list = list(map(int, input().split()))
set_dic = {}
for i in set_list:
    set_dic[i] = 0
cand_dic = {}

dfs()

is_answer = False
for k, v in cand_dic.items():
    if v > 1:
        is_answer = True
        break

if is_answer:
    print('YES')
else:
    print('NO')