Part5.4_완전탐색_부분집합 구하기(DFS)__합이 같은 부분집합

합이 같은 부분집합

import sys
#sys.stdin = open("input.txt", "rt")

def DFS(v):
    if v==n:
        sum = 0
        for i in range(n):
            if res[i] == 1:
                sum += a[i]
            if sum > stdNum:
                break
        if sum ==  stdNum:
            print("YES")
            sys.exit(0)

    else:
        res[v] = 1
        DFS(v+1)
        res[v] = 0
        DFS(v+1)

if __name__ == "__main__":
    n =int(input())
    a = list(map(int,input().split()))
    res=[0]*n
    stdNum = sum(a)/2 #16
    DFS(0)
    print("NO")

근데 코드가 좀 길다

선생님 코드

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, sum): # L은 인덱스 번호이다. 0번 인덱스는 사용하겠다 >> sum에 인덱스0값 더한다 // 0번 인덱스는 사용하지않겠다 >> sum 유지
    if sum>total//2:
        return #시간 복잡도 줄이기 위함이다.
    if L==n:
        sum = 0
        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")