https://www.acmicpc.net/problem/1182

---

1. 코드

import sys

def dfs(idx, sm, cnt):
    global answer
    if idx == n:
        if sm == s and cnt > 0:
            answer += 1
        return
    dfs(idx+1, sm+arr[idx], cnt+1)
    dfs(idx+1, sm, cnt)


answer = 0
n, s = map(int, sys.stdin.readline().rstrip().split())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

dfs(0, 0, 0)
print(answer)

---

2. 후기

배열의 index에 해당하는 원소를 포함하거나 포함 안하거나 두 가지 선택만 존재한다. 원래는 시간초과가 발생할 것 같아서 시도하지 않았는데, N의 범위가 최대 20이기 때문에 2^20의 경우의 수는 기껏해야 1048576(백만)이기 때문에 시간초과는 발생하지 않을 것이다.

dfs(idx+1, sm+arr[idx], cnt+1)  # 현재 arr[idx]포함
dfs(idx+1, sm, cnt)  # 현재 arr[idx] 미포함