[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

 

나의 코드

def DFS(n):
    if n==0:
        S=0
        for i in range(len(ch)):
            if ch[i]==1:
                S=S+arr[i]
        if (S==sum(arr)-S):
            print(S,sum(arr))
            print("Yes")       
    else:
        ch[n]=1
        DFS(n-1)
        ch[n]=0
        DFS(n-1)


n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0)
ch=[0]*(n+1)
DFS(n)

 해당 N개의 자연수를 arr에 입력 받은뒤 그 갯수 +1 만큼의 체크 배열을 생성한다.

그후 arr에 체크 배열과의 인덱스를 맞추기 위해 0번인덱스에 0을 넣는다.

 

그후 DFS 완전탐색을 진행하며 체크 리스트를 다 채운뒤 ch가 체크가 되있는 인덱스의 합을 구한다.

 

 

 

 

 정답코드

import sys
sys.stdin=open("input.txt", "r")
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")

 

 정답 코드는 나와 약간 다르다. DFS 탐색의 인자값으로 레벨과 합을 받는다.

그 후 탐색은 해당 숫자를 더한 값과 더하지 않은 값으로 양갈래로 나뉘어 탐색이 된다. 

그리고 Cut-edge로 sum>total//2를 넣어 의미없는 탐색을 커트했다.

 

위 코드도 좋은 접근인것 같다.