[백준] 부분수열의 합 - 파이썬 Python

https://www.acmicpc.net/problem/1182

완전탐색으로 풀기

파이썬의 combinations 함수를 통해 가능한 부분수열을 모두 구한다. 부분수열마다 합이 구하고자 하는 수와 같은지 비교한다.

시간복잡도가 O(n * 2^n) 이므로 n이 큰 경우 통과하지 못할것 같다. 다른 풀이가 생각나면 풀어볼것

import itertools

n, s = map(int, input().split())
sequence = list(map(int, input().split()))
result = 0

for i in range(1, n+1):
    for j in itertools.combinations(sequence, i):
        temp = list(j)
        if sum(temp) == s:
            result += 1

print(result)