[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 4

🚗 합이 같은 부분집합(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

import sys
sys.stdin = open("input.text", "rt")

N = int(input())
data = list(map(int, input().split()))

total = sum(data)

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 + data[L]) #현재 원소 추가하고 (L번 인덱스 추가) 다음으로 넘어감
        DFS(L+1, sum) #현재 원소 추가하지 않고 다음 인덱스로 넘어감 !

DFS(0,0) #처음 인덱스부터 돌아야하고, 처음 합은 0이니깐
print("NO") #프로그램 종료 안되면 NO니까 출력해주면 됨.

🚗 코멘트
DFS를 인덱스 단위로 접근하는 방식도 생각. 상태 트리, 즉 속하냐 속하지 않느냐를 판단할 수 있다면 DFS로 문제 풀 수 있겠다 생각하고 시작.
해당 원소(L번 인덱스) 포함 된다면 sum에 더해서 다음 인덱스로 포함되지 않는다면 그냥 보내는 방식으로 표현한 문제.

이렇게 푸는 방법도 체화해야함.