[백준]1182 부분수열의합

1. 풀이

모든 경우를 다 조사하면 된다. dfs(소스코드1)와 조합(소스코드2)으로 풀었다.

주의할 점은 "부분수열의 정의"와 "최대 경우의 수".

(1) 부분수열의 정의

수학에서, 수열의 부분수열(部分數列) 또는 부분열(部分列, subsequence)은 그 수열의 일부 항을 원래 순서대로 나열해 얻을 수 있는 수열이다. 예를 들면 크기 순으로 나열된 양의 짝수 2, 4, 6, ...은 크기 순으로 나열된 자연수 1, 2, 3, 4, 5, 6, 7, ...의 부분수열이다.

https://ko.wikipedia.org/wiki/%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4

(2) 최대 경우의 수

최대 경우의 수는 N=20일때, 20C1+20C2+20C3+...20C19+20C20 이 된다.

20C10 만 해도 엄청 클것같아서 완전탐색이 아닐 줄 알았는데 20C10은 184756밖에 안된다.

20C1 ~ 20C20의 결과

 

2. 소스코드

(1) dfs, 통과

from collections import deque
N,S=map(int,input().split())
L=list(map(int,input().split()))

stack=deque([[0,0]])
ans=0
while stack:
    sum,indx=stack.pop()
    if indx==N:
        continue
    # 해당숫자를 선택하지 않는 경우
    stack.append([sum,indx+1])

    # 해당숫자를 선택하는 경우
    if sum+L[indx]==S:
        ans+=1
    stack.append([sum+L[indx],indx+1])

print(ans)

 

(2) 조합,통과

from itertools import combinations
N,S=map(int,input().split())
L=list(map(int,input().split()))

ans=0
for j in range(1,N+1):
    comb=list(combinations([i for i in range(N)],j))
    for case in comb:
        sum=0
        for indx in case:
            sum+=L[indx]
        if sum==S:
            ans+=1
print(ans)