BOJ 1208 부분수열의 합 2

https://www.acmicpc.net/problem/1208
시간 1초, 메모리 128MB
input :

• N S(1 ≤ N ≤ 40, |S| ≤ 1,000,000)
• 정수(|정수| <= 100,000)

output :

• 합이 S가 되는 부분수열의 개수를 출력

---

부분수열의 합의 경우 연속적이지 않은 경우도 포함한다.

오늘의 선생님이시다.
https://dirmathfl.tistory.com/173

다른 분들의 경우 비트마스크를 이용하시길래 이건 좀 이따가 공부해보도록 하고 그나마 많이 본 재귀 형식으로 공부했다.
우선 수열을 반갈 해야한다. 경우의 수가 너무 크기 때문에 반으로 나눠서 한 쪽의 합들을 구해서 다른 한 쪽에서 찾아준다.

defauldict 를 이용하면 모든 키에 대해서 값을 리턴해주는데 초기화가 0으로 되어있다고 볼 수 있다.

그래서 dfs의 경우 각 idx로 들어 올 때. subtotal을 먼저 확인 하기 때문에 0 공집합일 때를 확인 하고.
0
-3
-7 0
-7 -3
순서로 움직인다.

end_idx를 n으로 두면서 모든 item들은 체크 하고 마지막에 ans에 걸리게 해준다.. 매우 똑똑

만약 s가 0이라면 ans가 count할 때에 공집합도 함께 카운트 하기 때문에 1을 빼줘야 한다.

import sys
from collections import defaultdict
sys.setrecursionlimit(10000)

n, s = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
left = defaultdict(int)
ans = 0


def dfs(idx, end_idx, subtotal, direction):
    global ans
    if idx == end_idx:
        if direction == 'right':
            ans += left[s - subtotal]
        else:
            left[subtotal] += 1
        return

    dfs(idx + 1, end_idx, subtotal, direction)
    dfs(idx + 1, end_idx, subtotal + data[idx], direction)


dfs(0, n // 2, 0, 'left')
dfs(n // 2, n, 0, 'right')

if s != 0:
    print(ans)
else:
    print(ans - 1)