[python] 백준 Silver2 1182.부분수열의 합

문제

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

1182번: 부분수열의 합

---

접근

백트래킹으로 모든 경우의 수의 합을 구해준다.

합이 s와 같으면 answer ++ 해서 부분수열의 갯수를 구해주먄된당

---

코드

n, s = map(int ,input().split())
number = list(map(int ,input().split()))
answer = 0

def dfs(i,total,number,visited):
    global answer,n,s
    if total == s:
        answer += 1

    for j in range(i+1,n):
        if visited[j] == 0:
            visited[j] = 1
            dfs(j, total+number[j],number,visited)
            visited[j] = 0

for i in range(n):
    visited = [0]*n
    visited[i] = 1
    dfs(i,number[i],number,visited)

print(answer)