부분수열의 합

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) )