아니.. 난 아직 멍청하다 (dfs)

#14225 부분수열의 합 https://www.acmicpc.net/problem/14225 

14225번: 부분수열의 합

 

유사한 문제를 가볍게 풀었던 경험이 있다.

 

쉬울거라고 생각했는데 자꾸 시간초과가 나서 짜증났다.

 

시간초과가 난 코드

N = int(input())
nums = list(map(int, input().split()))
visited = [False]*N
output = []

result = [False]*2000001


def solve(depth):
    result[sum(output)] = True

    if depth == N:
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            output.append(nums[i])
            solve(depth+1)
            output.pop()
            visited[i] = False


solve(0)
for b in range(1, 2000001):
    if not result[b]:
        print(b)
        break

이 코드는 중복되는 값이 실행된다.

 

이게 정답 코드

N = int(input())
nums = list(map(int, input().split()))
result = [False]*2000001


def solve(depth, s):
    if depth == N:
        return
    
    s += nums[depth]
    result[s] = True
    solve(depth+1, s)
    solve(depth+1, s-nums[depth])


solve(0, 0)
for b in range(1, 2000001):
    if not result[b]:
        print(b)
        break

 

중복이 발생하지 않는다.