백준 14225 부분수열의 합

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

import itertools
n = int(input())                        # 4
s = list(map(int, input().split()))     # 2 1 2 7
if n == 1:              # 수열의 크기가 1인 경우, 원소가 1이면 1, 1보다 크면 2 출력
    if s[0]!=1:
        print(1)
    else:
        print(2)
else:            # 수열의 크기가 1보다 큰 경우
    s.sort()     # 수열 정렬
    
    hap = set()  # 부분수열의 합 저장할 집합
    for i in range(1,n+1):      # 모든 경우의 수 조합
        l = list(itertools.combinations(s,i))

        for j in range(len(l)):
            hap.add(sum(l[j]))  # hap에 합 부분수열의 합 저장
    cnt = 1          # 1부터 있는 지 찾음
    hap = list(hap)
    hap.sort()       # 정렬

    for i in hap:    # 모든 부분수열의 합 저장한 리스트에서 1부터 있는지 찾음
        if cnt == len(hap):   # hap = [1,2,3,4](처음부터 끝까지 1씩 증가하면 len(hap)+1인 5 출력)
            print(sum(s)+1)
            break 
        if i == cnt:          # 1부터 그 수가 있는지 찾고 있으면 cnt += 1
            cnt += 1
        else:                 # 없으면 그 수 출력 (나올 수 없는 가장 작은 자연수)
            print(cnt)
            break