Python 1182번 부분수열의 합

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

1182번: 부분수열의 합

 

이 문제는 재귀 방식을 이용한 브루트 포스 방식으로 문제를 풀었다.

문제에서 조건이 크기가 양수인 부분 수열이기 때문에 수열의 크기가 0보다 크고 합이 s와 같을 경우에 cnt라는 리스트에 저장하도록 하여 cnt리스트의 개수가 출력되도록 하였다.

import sys
cnt=[]
input=sys.stdin.readline
def recur(i,res,sum,s,n):
    if sum==s and len(res)>0:
        cnt.append(0)
    for idx in range(i,n):
        res.append(ary[idx])
        sum+=ary[idx]
        recur(idx+1,res,sum,s,n)
        res.pop()
        sum-=ary[idx]

n,s = map(int,input().split())
ary = list(map(int,input().split()))
recur(0,[],0,s,n)
print(len(cnt))