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

문제

이번에 풀어볼 문제는 부분 수열의 합이다.

풀이과정

저번에 블로그에 정리한 암호 만들기 문제랑 거의 똑같아서 딱히 설명할 게 없다.

그냥 dfs로 풀어주면 된다.

최종 코드

n, s = map(int, input().split())
numbers = list(map(int, input().split()))
count = 0


def dfs(sum, idx):
    global count
	
    if sum == s and idx:
        count += 1
	
    #현재 인덱스보다 뒤에 숫자 중에서 선택해서 dfs
    for i in range(idx, n): 
        dfs(sum + numbers[i], i + 1)


dfs(0, 0)

print(count)