[인프런] 합이 같은 부분집합

---

문제설명

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때, 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 'YES'를 출력하고, 그렇지 않으면 'NO'를 출력하는 프로그램을 작성해라. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 한다.

입력조건

• 첫째 줄에 자연수 N(1 <= N <= 10)이 주어진다.
• 둘째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

출력조건

• 첫줄에 'YES' 또는 'NO'를 출력한다.

사고과정

• 상태트리를 그려서 어떻게 구현해야 할지 매우 고민했다.. 저번에 배운 체크 테이블을 정의해야 하나 싶었지만 그렇게 풀 순 없었다..
• 결국 풀이를 보았고 이번에는 DFS 함수 인자에 인덱스, 부분집합의 합을 넣어주어서 해당 인덱스의 원소를 부분집합에 포함시키는지 아닌지에 따라 상태트리 갈래 길을 결정했다.
• 인덱스의 원소는 계속 증가시키되 부분합에 해당 원소가 누적해서 더해지면 해당 원소를 부분집합에 포함시켰다는 의미이고 이전 누적값을 그대로 해서 간다면 부분집합에 포함시키지 않는다는 것을 의미하는 것이다..!!!!!
• 그리고 시간복잡도를 줄이기 위한 기술도 한 가지 배웠는데, 해당 문제에서 누적 합이 전제 원소의 합을 2로 나눈 것보다 커지게 된다면 그 이후의 탐색은 하지 않아도 된다! 그래서 중간에 if 조건문을 추가로 두어서 시간복잡도를 줄일 수 있다.
• 또한 'YES' 조건을 만족할 시 바로 함수를 빠져나오는 기법을 활용하기 위해 sys.exit(0) 이라는 문법을 사용할 수 있다고 한다. 해당 문법은 프로그램을 아예 종료시킨다. 하지만 이러한 sys 문법을 사용할 수 없는 테스트 환경이 있을 수 있기 때문에 그럴 경우에는 flag 라는 새로운 변수를 두어서 처리한다. 이 두가지 방법에 대한 풀이를 모두 살펴보자!

풀이(스스로 못 푼 풀이)

- sys.exit(0)을 활용한 풀이

n = int(input())
arr = list(map(int, input().split()))
total = sum(arr)

def DFS(idx, sum_val):
    # 도중에 더이상 가능성 없는 경우 바로 중단하여 시간복잡도 줄이기!
    if sum_val > (total // 2):
        return
    # 인덱스가 끝에 다다르고 +1 되었을 경우 종단 조건!
    if idx == n:
        if sum_val == (total - sum_val):
            print('YES')
            sys.exit(0)  # 프로그램 자체를 종료시키기! -> 근데 못쓸경우는! flag 함수 새로 두어야 함
    else:
        DFS(idx+1, sum_val+arr[idx])  # 현재 idx에 있는 원소 사용하기로 결정!
        DFS(idx+1, sum_val)           # 현재 idx에 있는 원소 사용하지 않기로 결정!


# main
DFS(0, 0)  # 0번 인덱스, 누적합=0
print('NO')

- sys를 사용하지 않고 새로운 flag 변수를 두어 푼 풀이

n = int(input())
arr = list(map(int, input().split()))
total = sum(arr)
flag = False

def DFS(idx, sum_val):
    global flag
    if flag:
        return
    if sum_val > (total // 2):
        return
    if idx == n:
        if sum_val == (total - sum_val):
            print('YES')
            flag = True
    else:
        DFS(idx+1, sum_val+arr[idx])  # 현재 idx에 있는 원소 사용하기로 결정!
        DFS(idx+1, sum_val)           # 현재 idx에 있는 원소 사용하지 않기로 결정!

DFS(0, 0)  # 0번 인덱스, 누적합=0
if not flag:
    print('NO')