[백준] 1182 "부분수열의 합" 백트래킹 -python

 

알고리즘

 공집합을 제외한 2^n - 1개의 부분집합에 대해 모두 탐색을 실시한다. 이때 부분집합의 개수는 원소를 포함시킬것인가 아닌가 2가지로 나뉘어 2^n개임을 생각해보면 빽트래킹을 통해 쉽게 구할 수 있다고 생각하였다.

 

소스코드

# 부분수열의 합
import sys
n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

result = 0
if s == 0: # s = 0 인경우 공집합을 제외
    result = -1
def func(idx, S):
    global result
    if idx > n-1:     
        if S == s:
           result += 1
        return
    
    func(idx + 1, S + arr[idx]) # 해당 요소 선택
    func(idx + 1, S) # 해당 요소 선택x
            
func(0, 0)
print(result)