14225: 부분수열의 합

import sys

def dfs(node_idx):
    check = sum(nodes)
    result[check] = check

    for i in range(node_idx, N):
        if not visit[i]:
            nodes.append(S[i]); visit[i] = True
            dfs(i)
            nodes.pop(); visit[i] = False

N = int(input())
S = list(map(int, sys.stdin.readline()[:-1].split()))

visit = [False] * (N+1); nodes = []; result = [0] + [-1 for _ in range(2000000)] # 1 <= N <= 20, 1 <= S <= 100000
dfs(0)
print(result.index(-1))

• 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력해야함
• dfs 순회를 하기 전에 먼저 result 리스트를 이용해 나올 수 있는 부분 수열의 합의 모든 공간을 할당해서 -1로 채워넣음
• dfs 순회를 하면서 모든 부분 수열의 합을 갱신해주고, result 리스트에서 -1의 값을 갖고 있는 index들 중 가장 작은 index가 정답임