합이 같은 부분집합

생성일: 2022년 2월 1일 오후 7:36

구현 코드

# 합이 같은 부분 집합 (DFS)
import sys
sys.stdin = open("input.txt" ,"rt")

def DFS(index, l):
    if index == len(l):
        s = set()
        for i in range(len(l)):
            if ch[i] == 1:
                s.add(l[i])
        differenceSet = set(l) - s
        if sum(differenceSet) == sum(s):
            return True
        return False
    else:
        ch[index] = 1
        isSame = DFS(index+1, l)
        if isSame:
            return isSame
        ch[index] = 0
        isSame = DFS(index+1, l)
        return isSame
  
    
if __name__ == "__main__":
    n = int(input())
    ch = [0]*n
    l = list(map(int, input().split()))

    res = DFS(0, l)
    if res:
        print("YES")
    else:
        print("NO")

모범 답안

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")

차이점

• 기본적인 로직은 같다.
• 내가 구현한 코드에서는 부분집합을 구하고 구해진 부분집합의 원소들의 합을 구하는 절차이지만 모범답안에서는 부분집합을 구하는 것이 아니라 원소들의 합을 곧바로 구하여 비교하였다.
• 두 부분집합의 합이 같다는 것을 확인하고 나서 내가 구현한 방법은 isSame변수를 통해 재귀 합수가 최종적으로 True를 리턴하도록 하였다.
• 모범 답안에서는 해당 상황에서 sys.exit(0) 을 통해 더이상 합수를 진행시키지 않고 강제 종료 시키는 방법을 사용하였다.