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

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

 

부분수열은 상태트리로 1 0 으로 뻗어나가면 풀기 편리하다.

처음에 계속 예제문제가 2가 나와서 아이러니해서 고민을 했는데 문제를 잘 읽어보니 크기가 양수라는 조건이 있어서 공집합을 제외시켜줘야 답이 출력되는 형태였다.

그래서 DFS변수를 L 깊이, sum 합, k 부분집합의 개수 로 설정하고 양수가 아니면 cnt를 증가시켜주지 않는 조건을 추가하여 답을 출력하게 만들었다.

 

n, s = map(int, input().split())
arr = list(map(int, input().split()))


cnt = 0
def DFS(L, sum, k):
    global cnt

    if L == n:
        if s == sum and k!=0:
            cnt+=1
            
    else:
        DFS(L+1, sum+arr[L],k+1)
        DFS(L+1, sum, k)

DFS(0,0,0)

print(cnt)

 

완성