부분수열의 합 2

• 부분수열의 합에서 n의 범위를 늘린 문제
• 부분수열의 합는 O(2^n) 알고리즘으로도 풀 수 있었지만, 이 문제는 반드시 meet in the middle 테크닉을 써서 O(2^(n/2))으로 풀어야만 한다. 풀이는 부분수열의 합 참조

"""Solution code for "BOJ 1208. 부분수열의 합 2".

- Problem link: https://www.acmicpc.net/problem/1208
- Solution link: http://www.teferi.net/ps/problems/boj/1208

Tags: [MeetInTheMiddle]
"""

import collections


def main():
    N, S = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]

    first, second = [0], [0]
    for num in nums[:N // 2]:
        first.extend([num + x for x in first])
    for num in nums[N // 2:]:
        second.extend([num + x for x in second])
    second_counter = collections.Counter(second)

    answer = sum(second_counter[S - f] for f in first)
    if S == 0:
        answer -= 1
    print(answer)


if __name__ == '__main__':
    main()