[백준] #1182 부분수열의 합-python

> 문제 링크: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

> 답압 

 

파이썬

1. itertools 사용 ver

from itertools import combinations
import sys
input = sys.stdin.readline
n, s = map(int, input().split())
a= list(map(int, input().split()))
cnt =0
for i in range(n):
    for perset in combinations(a,i+1):
        # print(perset)
        if sum(perset)==s:
            cnt+=1
print(cnt)

2. backtracing ver 

# itertools없이 
import sys
def dfs(now):
    global n,s,a,tempsum,cnt
    # 만약 트리의 끝에서 한칸 더가면 끝
    if now ==n:
        return
    # 만약 지금까지의 합이 s라면 count +1 (뒤에도 +1-1 이 나올 수 있으니까 더 해봐야함)
    if tempsum +a[now] ==s:
        cnt+=1

    # 0을 더하고 (즉 아무것도 하지 않고 내려가기)
    dfs(now+1)
    
    # 현재 값을 더하고 내려기가
    tempsum += a[now]
    dfs(now+1)

    tempsum -=a[now]


input = sys.stdin.readline
n, s = map(int, input().split())
a= list(map(int, input().split()))
cnt =0
tempsum=0
dfs(0)
print(cnt)