https://www.acmicpc.net/problem/1182
- 나의 풀이
from itertools import combinations
import sys
def _buket_sum(n_list, N, S):
answer = 0
for i in range(1, N + 1):
for combi in combinations(n_list, i):
if sum(combi) == S:
answer += 1
return answer
N, S = map(int, sys.stdin.readline().rstrip().split())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))
print(_buket_sum(n_list, N, S))
- 시간 복잡도
for i in range(1, N + 1) : 1부터 N까지 조합을 순회
for combi in combinations(n_list, i) : 조합을 찾는 순열 : 2**N 시간
해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O(2**n) )
