합이 같은 부분집합

문제 : 

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

 

코드는 다음과 같다. (다른 사람의 코드를 참고하였습니다.)

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)


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

DFS, BFS를 공부했지만, 막상 이런 문제가 나오면 적용 못 할 것 같다.. 그만큼 아직 풀어본 문제가 적다는거겠지..

위 알고리즘을 확실하게 이해하기 위해 따로 정리해보았다.

인덱스를 1씩 늘려가며 DFS함수를 실행해 모든 값을 탐색한다.

DFS 실행하는 경우는 2가지로 나뉘는데, 그 인덱스를 선택했을 때와 선택하지 않았을 때로 나뉜다.

그리고 sum 값이 total//2 보다 크면 return해주어 빠져나온다. 굳이 이 조건문이 없어도 답을 찾는데 문제는 없지만, n이 크면 클수록 시간을 더욱 줄일 수 있을 것이다.

L == n (종료 지점인 경우) and sum == total-sum (부분 집합의 합이 총합에서 부분집합의 합을 뺀 나머지와 같은 경우)에 YES를 출력해주고 종료해주면 된다.

아직 실력은 부족하지만 재미는 있는 것 같다.. 얼른 어려운 문제를 풀어 희열 느끼고 싶ㄷ..

 

 

from itertools import combinations
from itertools import chain
lst = [10,20,30,40]
ans = []
for i in range(1,5):
  ans.append(list(map(list,combinations(lst, i))))

ans = list(chain(*ans))
print(ans)
res = []
for i in range(len(ans)):
  for j in range(i+1, len(ans)):
    if len(set(ans[j]) & set(ans[i])) == 0:
      if sum(ans[i]) == sum(ans[j]):
        print(i,ans[i], ans[j])
        res.append(sum(ans[i]))
  
print(res)