半分全列挙

C - 無駄なものが嫌いな人

import sys
import math
import heapq
import itertools
from collections import deque
from collections import defaultdict
from functools import reduce

def has_bit(n, i):
    return (n & (1<<i) > 0)

# main
def main():
    N, X = list(map(int, input().split()))
    A = []
    B = []
    for i in range(0, N):
        w = int(input())
        if i%2 == 0:
            A.append(w)
        else:
            B.append(w)

    dic = defaultdict(int)
    for n in range(1<<len(B)):
        s = 0
        for i in range(N):
            if has_bit(n, i):
                s += B[i]
        dic[s] += 1

    ans = 0
    for n in range(1<<len(A)):
        s = 0
        for i in range(N):
            if has_bit(n, i):
                s += A[i]
        ans += dic[X-s]     

    print(ans)
# エントリポイント
if __name__ == '__main__':
    main()