[백준] 1182(파이썬) - 부분수열의 합

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

1182번: 부분수열의 합

• 이 문제는 다양한 방법이 있을 거 같지만 일단은 직관적으로 풀어봤다.
• 그냥 주어진 입력값의 조합을 다 구해서 그 조합들의 합이 S가 될 때 cnt를 1씩 올려서 구현했는데 시간 초과가 날줄 알았는데 시간 초과 없이 통과했다.
• 두 번째 구현은 dfs로 구현했다.
• idx값과 Sum 변수를 함수 변수로 넘겨주고, idx는 1씩 더해서 재귀를 사용했고 Sum을 통해서 그 이전값과 그 값을 더하는 방식으로 재귀를 구현하였다.

import sys
input = sys.stdin.readline
from itertools import combinations

n,s = map(int,input().split())
data = list(map(int,input().split()))
com_data = []
for i in range(len(data)):
    com_data.append(list(combinations(data,i+1)))

cnt = 0
for i in range(len(com_data)):
    for j in range(len(com_data[i])):
        if sum(com_data[i][j]) == s:
            cnt += 1
print(cnt)
#############################dfs로 백트래킹 구현
import sys
input = sys.stdin.readline
def dfs(idx, Sum):
    global cnt
    if idx >= n:
        return
    Sum += data[idx]
    if Sum == s:
        cnt += 1
    dfs(idx + 1, Sum - data[idx])
    dfs(idx + 1, Sum)
n, s = map(int, input().split())
data = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
print(cnt)