[백준 1182] 부분수열의 합 - python (solved.ac - 실버 2)

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

1182번: 부분수열의 합

풀이

문제를 보았을때 알수있는 힌트

모든 경우의 수를 다 확인하면서 S가 되는지 확인하는 함수를 만들어 풀면 될듯함

 

import sys

input = sys.stdin.readline
n, s = map(int, input().split())
s_list = list(map(int, input().split()))
count = 0

def dfs(i,sum):
    global count
    if i>=n:
        return
    sum+=s_list[i]
    if sum == s:
        count+=1
    dfs(i+1,sum-s_list[i])
    dfs(i+1,sum)

dfs(0,0)
print(count)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1182.py