[BOJ] 1182

문제링크: https://www.acmicpc.net/problem/1182

문제 설명은 간단하다.
N개의 정수로 이루어진 수열이 있을 때, 더한 값이 S인 부분수열의 개수를 구하는 문제이다.

만약 -7 -3 -2 5 8의 수열이 있을 때, 부분수열의 경우는 아래와 같다.

경우의 수는 두가지이다.
1. 현재의 값을 더하지 않는다
2. 현재의 값을 더한다

또한 해당문제에서는 공집합을 제외해야 하므로, 만약 S가 0일 경우 공집합의 경우를 제외시켜줘야 한다.
이를 구현한 코드는 아래와 같다.

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def solution(curr, sum):
    global cnt
    
    if curr == N:
        if sum == S:
            cnt += 1
        return

    solution(curr+1, sum)
    solution(curr+1, sum+arr[curr])
    
solution(0, 0)
if S == 0: cnt -= 1
print(cnt)