백준 14225 부분수열의 합(+ 재귀)

import sys
from itertools import combinations

n=int(input())
array=list(map(int,sys.stdin.readline().split()))
result=list()

for i in range(1,n+1):
    result.append(combinations(array,i))

tempA=list()
for i in result:
    for j in i:
        tempA.append(sum(j))

tempA.sort()
tempA=set(tempA)
max_temp=max(tempA)

tempB=set()
for i in range(1,max_temp+1):
    tempB.add(i)

temp_result=tempB-tempA

if len(temp_result)==0:
    print(max_temp+1)
else:
    print(min(temp_result))
    

이 문제는 방금전의 문제와 비슷하다.

n개의 수를 1부터 n 까지의 조합을 구하여서 그 각 합들을 result 에 넣게된다.

​

result에 넣은후에 나온 경우들의 합을 새로운 list 에다 넣는다

나는 그 list를 tempA 라 하겠다.

tempA 에 각 합들을 넣은뒤 정렬한후 집합으로 새로 만든다.

집합으로 새로 만드는 이유는 중복되는 값은 집합에 들어올수 없기에 각 수는 한번만 나타나게 될것이기 떄문이다.

​

그러고 tempB 라는 1 부터 max(tempA) 까지의 수가 들어있는 집합을 만들어서

temp_result 라는 변수에 tempB- tempA 의 차집합을 진행한다.

만약 차집합을 했는데 값이 없으면 max(tempA)+1 이라는 수를 나타내면 되고

값이 있으면 min(temp_result)를 하여 차집합한 수중 가장 작은 값을 나타내면 된다.

import sys

n=int(input())
array=list(map(int,sys.stdin.readline().split()))
result=list()

s=0
def subset(idx,a):
    if idx>=n:
        return


    a+=array[idx]
    result.append(a)

    subset(idx+1,a)
    subset(idx+1,a-array[idx])


subset(0,0)
max_num=max(result)
result.sort()
result=set(result)

resultB=set()
for i in range(1,max_num+1):
    resultB.add(i)

temp_result=resultB-result

if temp_result:
    print(min(temp_result))
else:
    print(max_num+1)
    

다음은 재귀 방식이다.

밑에 부분은 다똑같지만 나는 combination 으로 모든 경우의 수를 뽑아준 반면에 재귀 방식은 선택 or 선택 x 방식으로 경우의 수를 뽑아준다.

그리고 밑의 부분은 다 같다.