[완전탐색][상태 트리] - 합이 같은 부분집합(DFS)

문제

주어진 n개의 요소를 가진 리스트에서 부분 집합이 나머지 부분 집합과 합이 같다면 합이 같은 부분집합이라고 한다. 

이때 합이 같은 부분집합이 있다면 YES를 없다면 NO를 출력하세요

문제 풀이

def DFS(level,s):
    global flag
    if flag == 0:
        return
    if level == n:
        if s == (total_sum - s):
            print("YES")
            flag = 0
    else:
        DFS(level + 1, s + a[level])
        DFS(level+1, s)


if __name__ =="__main__":
    n = int(input())
    a =list(map(int,input().split()))
    total_sum = sum(a)
    flag = 1
    DFS(0,0)
    if flag:
        print("NO")

• 앞선 포스팅과 같이 상태 트리를 사용해서 문제를 푼다.
• 이때 두가지 매개변수를 사용하는데 하나는 인덱스(트리에선 같은 위치에 있는 노드들을 같은 레벨에 있다 표현한다.), 또 다른 하나는 해당 변수를 도는 부분 집합의 합을 구하는 변수이다. 
• 이때 n개의 원소가 들어있으니 Level이 n만큼 있다면 조건을 확인하고 조건을 만족하면 YES를 출력하며 해당 함수를 return을 사용해 종료 시킨다. 
• 이때 모든 리스트의 부분집합을 돌면서도 답을 구해내지 못했다면 NO를 출력해준다. 
• level의 경우엔 어찌하든 계속 늘어나기에 level + 1을 해주며 진행하고 부분집합의 합의 경우엔 사용하는 경우엔 +해당 인덱스의 값 사용하지 않는 경우엔 더해주지 않는다.