[ BOJ 1182 ] 부분 수열의 합(Python)

문제

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

n개로 이루어진 수열에서 만들 수 있는 부분 수열의 합이 s가 될 때의 경우의 수를 구하는 문제다.

---

문제 풀이

[1,3,5] 로 만들 수 있는 부분 수열은
[1], [3], [5], [1, 3], [1, 5], [3, 5], [1, 3, 5] 이다.

이 부분 수열의 합은 아래와 같이 나타낼 수 있다.

1	3	5	합
O	X	X	1
X	O	X	3
X	X	O	5
O	O	X	4
O	X	O	6
X	O	O	8
O	O	O	9

즉 어떤 숫자에 대해서 더했을 때와, 더하지 않았을 때를 고려해주면 된다.

dfs(index+1, n, s, cnt) # 더하지 않았을 때
dfs(index+1, n, s, cnt + nums[index]) # 더했을 때

---

코드

import sys
input = sys.stdin.readline

total_cnt = 0

def dfs(index, n, s, cnt):
    global total_cnt
    if index == n: 
        return
    if cnt + nums[index] == s:
        total_cnt += 1
    dfs(index+1, n, s, cnt) # 0 
    dfs(index+1, n, s, cnt + nums[index]) # num

n, s = map(int, input().rsplit())
nums = sorted(list(map(int, input().rsplit())))

dfs(0, n, s, 0)

print(total_cnt)