백준 1182 파이썬 python : 부분수열의 합 @@황소처럼 우직하게@@

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
num_list = list(map(int, input().split()))

ans = 0
def subSet(idx, total):
    global ans

    if idx >= n:
        return
    total += num_list[idx]
    if total == s:
       ans += 1
    subSet(idx + 1, total - num_list[idx])
    subSet(idx + 1, total)

subSet(0, 0)
print(ans)

jaimemin 님의 c++ 풀이를 참고하였다.

재귀로 풀었다.

Solution

각 원소는 그 원소가 포함되었는지 안되었는지로 나뉘어진다.

길이가 0인 것이 계산되면 안되기에

total += num_list[idx]

 

재귀 함수에서 위 코드처럼 먼저 더하고 시작한다.