백준 1182 부분수열의 합 (파이썬)

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

1182번: 부분수열의 합

dfs 조합으로 모든 경우에 대한 합을 구하고 S와 같으면 ans을 증가시킨다

import sys

input = sys.stdin.readline

def dfs(cnt, idx, c):
    global ans
    if cnt == c:
        res = 0
        for i in range(n):
            if select[i]:
                res += a[i]
        if res == s:
            ans += 1
        return

    for i in range(idx, n):
        select[i] = 1
        dfs(cnt + 1, i + 1, c)
        select[i] = 0


n, s = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for c in range(1, n+1):
    select = [0 for _ in range(n)]
    dfs(0, 0, c)
print(ans)