6.4 합이 같은 부분 집합 (DFS)

문제

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

---

내 풀이(2% 부족한 풀이)

import sys

def DFS(v):
    list=[]
    result="NO"
    if v==n:
        for i in range(n):
            if ch[i]==1:
                list.append(num_set[i])
        if 2*sum(list)==sum(num_set):
            result="YES"
            print(result)
            sys.exit(0)
            return
        
    else:
        ch[v]=1
        DFS(v+1)
        ch[v]=0
        DFS(v+1)
    


if __name__=="__main__":
    n=int(input())
    num_set=list(map(int,input().split()))
    ch=[0]*n
    DFS(0)
    print("NO")

 

올바른 풀이(강의)

import sys

def DFS(L, sum):
    if sum>total//2:
        return
    #합계가 토탇//2보다 커지면 더 이상 함수를 돌리는 의미가 없기에 여기서 커트한다
    #-->시간 복잡도 줄이기 위해서
    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")

-sys.exit

DFS 함수를 계속 돌려서 YES No 판별을 돌릴 때

yes 하나만 혹은 no 하나만 출력하는 것을 처리하지 못했다.

이를 강의에서는 sys.exit(0)를 통해 해결하였다.

YES값이 나오면 바로 프로그램을 종료시키는 것이다.

그리고 만약 YES가 나오지 않을 때 main 부분에서 NO를 출력하도록 설정했다

-->프로그램 종료를 통해 함수를 아예 종료시키는 방법과 그냥 YES 없이 통과할 경우 NO를 출력하도록 

메인에 print문 작성하는 방법을 기억해야 됨! 

 

-함수 인자 2개 받기

내 풀이에서는 그 때마다 sum(list) 함수를 통해서 합계를 구하였으나 강의에서는 

합계를 함수의 인자로 받아서 처리했다.

 

-시간 복잡도

if sum>total//2:
        return
    #합계가 토탇//2보다 커지면 더 이상 함수를 돌리는 의미가 없기에 여기서 커트한다
    #-->시간 복잡도 줄이기 위해서