합이 같은 부분집합
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.txt", "r")
def DFS(L, sum): #L은 인덱스 또는 레벨을 의미
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")
'파이썬 알고리즘 > 완전탐색과 DFS기초' 카테고리의 다른 글
6. 중복순열 구하기(DFS) (0) | 2022.11.07 |
---|---|
5. 바둑이 승차 - Cut Edge Tech (0) | 2022.11.07 |
3.부분집합 구하기(DFS) (0) | 2022.11.06 |
2. 이진탐색트리 순회 (0) | 2022.11.06 |
1.재귀함수를 이용한 이진수 출력 (0) | 2022.11.06 |