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(x) :
if x==n:
for i in range(n) :
if s.get(i)!=0:
print(s.get(i), end=' ')
print()
return
else :
s[x]=s[x]
DFS(x+1)
s[x]=0
DFS(x+1)
if __name__=='__main__' :
#차집합 성질 이용하면 될 듯
n=int(input())
s=dict([(k,v) for k,v in enumerate(list(map(int, input().split())))])
DFS(0)
==>1 3 5 6 7 10
1 3 5 6 7
1 3 5 6
1 3 5 6
1 3 5
1 3 5
1 3 5
1 3 5
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
이런식으로 나온다 - 원인 발견해보기
def DFS(L,sum) :
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') #YES안나와서 프로그램이 종료가 안됐으면 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') #YES안나와서 프로그램이 종료가 안됐으면 NO출력하는 것