[알고리즘] 백준1182 부분수열의 합 - 파이썬

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

1182번: 부분수열의 합

 

[풀이 코드]

from sys import stdin

input = stdin.readline

array = []
N, S = map(int, input().split())
array = list(map(int, input().split()))

s = []
cnt = 0
def dfs(start):
    global cnt
    if len(s) > 0 and sum(s) == S:
        cnt += 1

    for i in range(start, N):
        s.append(array[i])
        dfs(i+1)
        s.pop()

dfs(0)
print(cnt)

• 백준의 N과 M시리즈를 다 풀고 이 문제를 풀어서 그런가 if문안에 return문을 넣어 계속 틀렸다. 그 부분만 수정했더니 정답.. 
• 다른 풀이들을 보니 대부분 dfs로 풀었고 dfs함수 안에서 현재 인덱스의 원소를 넣느냐, 빼느냐로 나눠서 재귀를 하는 것 같았다.