파이썬 알고리즘-45 (DFS/BFS) 합이 같은 부분집합

45.합이 같은 부분집합(DFS : 아마존 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면
”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의
집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이16으로 같은 경우가 존재하는 것을 알 수 있다.

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

▣ 입력예제 1
6 1
3 5 6 7 10

▣ 출력예제 1
YES

내 코드

def dfs(v,sum):
    if v>n-1:
        ch.append(sum)
        for i in ch:
            if ch.count(i)==2:
                print("YES")
                break
        
    else:
        sum+=lst[v]
        dfs(v+1,sum)
        sum+=0
        dfs(v+1,sum)
    print("NO")

n=int(input())
lst=list(map(int,input().split()))
ch=[]

dfs(0,0)

논리 전개는 초반에 비슷했는데 합을 어떻게 처리할지에서 망했다. NO출력하는 것도 어떻게 해야할지 몰라서 매번 출력되어버림

풀이

def DFS(L, sum):
    if sum>total//2:
        return
    if L==n:
        if sum==(total-sum):
            print("YES")
            sys.exit(0)
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

if __name__=="__main__":
    n=int(input())
    a=list(map(int, input().split()))
    total=sum(a)
    DFS(0, 0)
    print("NO")

반성점

• 항상 직전 문제에서 배운 방법밖에 생각이 안난다.

배운 것

• break vs sys.exit(): break는 반복문에서만 사용할 수 있다. 함수에서 쓰려면 sys.exit()을 쓰거나, sys를 사용할 수 없는 경우 switch를 1 또는 0으로 만들어 0일 때 함수를 종료하는 방식을 써야 한다.