[백준][파이썬] 14425 부분수열의 합(2)

[핵심]

1. 부분수열의 합(1) 과 같이 수열을 재귀함수를 통해서 생성한다

2. check라는 boolean형 리스트를 만들어주고, SUM(수열) 을 통해서 해당 숫자를 True로 설정한다

3. False(즉 나오지 않은 수열의 합) 중 가장 작은 수를 출력하다

 

시간이나 메모리가 괜찮으려면?

모두 저장할 필요는 없고, sum(수열)이 기존의 수보다 크다면 저장안하고 버려도 된다. 

 

n = int(input())
numlist = list(map(int,input().split(" ")))
numlist.sort()
visited = [False for i in range(n)]

check = [1] + [0 for j in range(2000000)]
def recu(limit,cnt,lit,space,visit):
    global check
    if len(space) == limit:
        if check[sum(space)] == 0:
            check[sum(space)] = 1
            return
        else:
            return

    for i in range(cnt,n):
        if visit[i] == False:
            space.append(lit[i])
            visit[i] = True
            recu(limit,i+1,lit,space,visit)
            space.pop()
            visit[i] = False
    return

for i in range(1,n+1):
    #n은 선택 개수, cnt는 반복 횟수
    recu(i,0,numlist,[],visited)

for ct,i in enumerate(check):
    if i == 0:
        print(ct)
        break