브루트포스의 일종으로, 문제를 절반으로 나눠서 양쪽 절반에서 모든 경우를 다 해보는 방법이다.
탐색할 때 시간복잡도를 많이 줄일 수 있다.
별 다른건 없고 그냥 똑같은 과정을 왼쪽 오른쪽 반반 나눠서 각자 수행한 다음 그 결과들을 보고 답을 내는 것이다. (딱히 재귀도 아님)
import sys
input = sys.stdin.readline
from itertools import combinations
from bisect import bisect_left, bisect_right
# 부분수열의 합을 구하는 완전탐색 방식
def getSum(nums, sums):
for i in range(1, len(nums)+1):
for c in combinations(nums, i):
sums.append(sum(c))
sums.sort() # 이분탐색을 사용해야하기 때문에 정렬 필요
N, S = map(int, input().split())
numbers = list(map(int, input().split()))
left = numbers[:N//2] # 왼쪽절반
right = numbers[N//2:] # 오른쪽절반
left_sum = [0] # left(왼쪽절반)의 부분수열의 합을 담는 곳
right_sum = [0] # right(오른쪽절반)의 부분수열의 합을 담는 곳
getSum(left, left_sum) # 왼쪽절반에서 부분수열의 합 구하기
getSum(right, right_sum) # 오른쪽절반에서 부분수열의 합 구하기
answer = 0
for l in left_sum:
# right_sum에 S-l이 몇개 있는지는 이분탐색으로 구함
answer += bisect_right(right_sum, S-l) - bisect_left(right_sum, S-l)
if S == 0: # 왼쪽에서 0, 오른쪽에서 0 선택했을 때 예외처리
answer -= 1
print(answer)