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 방식으로 경우의 수를 뽑아준다.
그리고 밑의 부분은 다 같다.