[백준, 1182번] 부분수열의 합

# 비트 연산자를 이용해서 내가 푼 방식
# 브루트 포스 문제다 보니 괜찮다고 생각했음
# 다만 단점은 역시 리스트에 하나씩 다 넣고 sum 메서드도 사용하고 초기화 하다보니
# 많은 시간이 소요된다는 단점이 있음
import sys
input = sys.stdin.readline
n,s = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
for i in range(1 << n):
    li = []
    for j in range(n):
        if i & (1<<j): li.append(a[j])
    if sum(li) == s and li != []: 
        cnt += 1
print(cnt)

# 다른 사람의 코드를 참고한 풀이
# 재귀를 사용해 푼 방식
# 가변적인 start로 i의 값이 변하는 것을 이용했음.
import sys
input = sys.stdin.readline
n,s = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
li = []
def subsequence(start):
    global cnt
    if sum(li) == s and li != []: cnt += 1
    for i in range(start, n):
        li.append(a[i])
        subsequence(i+1)
        li.pop()
subsequence(0)
print(cnt)