[백준] 14225번(부분수열의 합)

백준 14225번

최종 제출 코드

n = int(input())
array = list(map(int, input().split()))
visited=[0]*n
stack = []
result = {}

def dfs(index):

  if stack:
    result[sum(stack)] = 1
    
  for i in range(index, n):
    if not visited[i]:
      stack.append(array[i])
      visited[i] = 1
      dfs(i+1)
      stack.pop()
      visited[i] = 0

dfs(0)

for i in range(1,2000001):
  if i not in result:
    print(i)
    break

◼️ dfs를 이용하여 모든 부분집합을 구함

• 모든 부분집합의 원소의 합을 구함
• 이를 딕셔너리에 저장(나중에 결과값을 출력할 때 빠르게 접근하기 위함)
• 자연수를 키값으로 접근하여 구성할 수 없는 가장 작은 자연수 출력