[김태원 알고리즘] 합이 같은 부분집합 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(idx):
    global isExist
    if idx > len(lst) - 1:
        tot = 0
        for i in range(N):
            if ck[i] == 1: # 사용된 원소들
                tot += lst[i] # 누적
            else: # 사용되지 않은 원소들
                tot -= lst[i] # 다시 빼기
        if tot == 0:
            isExist = True
    else:
        ck[idx] = 1
        DFS(idx+1)

        ck[idx] = 0
        DFS(idx+1)

N = int(input())
lst = list(map(int, input().split()))

ck = [0] * N
isExist = False
DFS(0)

if isExist:
    print('YES')
else:
    print('NO')

다른 풀이 - sys 사용

import sys # ✅ 
def DFS(idx, partialSum):
    if idx == N:
        if partialSum * 2 == tot:
            print('YES')
            sys.exit(0) # ✅ 함수 종료가 아니라 프로그램 종료
    else:
        DFS(idx + 1, partialSum + lst[idx]) # lst[idx] 값을 사용 O
        DFS(idx + 1, partialSum) # lst[idx] 값을 사용 X

N = int(input())
lst = list(map(int, input().split()))

tot = sum(lst)
DFS(0, 0)
print('NO') # 프로그램이 종료되지 않고 왔다면

다른 풀이 - sys 사용X

혹시 sys.exit(0)을 사용하지 말라는 전제조건이 있는 상황을 대비한다면, flag 변수를 통해 exit() 없이도 구현할 수 있다.

def DFS(idx, partialSum):
    global isExist
    if idx == N:
        if partialSum * 2 == tot:
            isExist = True
    else:
        DFS(idx + 1, partialSum + lst[idx]) # lst[idx] 값을 사용 O
        DFS(idx + 1, partialSum) # lst[idx] 값을 사용 X

N = int(input())
lst = list(map(int, input().split()))

tot = sum(lst)
isExist = False
DFS(0, 0)

if isExist:
    print('YES')
else:
    print('NO')

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기