❗[알고리즘]합이 같은 부분집합

문제

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

[해설코드]

import sys
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")

1. DFS함수를 구성할 때 종료시점을 설정하는 것이 중요하다.
   if문을 통해 DFS함수의 종료시점을 설정한다.
2. 시간복잡도를 줄이기 위해서 sum>total//2 조건을 붙여 함수를 중단시킨다.
3. DFS(L+1,sum+a[L])은 a리스트의 L번 인덱스의 숫자를 더하고 그래프에서 왼쪽으로 뻗어나간다.
4. DFS(L+1,sum)은 a리스트의 L번 인덱스의 숫자를 더하고 그래프에서 오른쪽으로 뻗어나간다.