[백준 1182번 Python] 부분 수열의 합

완전 탐색과 백트래킹을 활용한 기본 문제.

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

1182번: 부분수열의 합

사람 허파 뒤집는 문제였다..진심

부분 수열의 합 문제 풀이 Check point

1. 재귀함수를 사용하여 푸는 문제. 
     현재 인덱스에 있는 값을 더하는 경우와, 더하지 않고 다음 인덱스로 넘어가는 경우를 나누어 구현
2. 리스트 내의 숫자에 따라 모든 조합을 확인하지 않을 수 있으므로 depth == N 의 조건문을 넣어줄 것.
     ex) S가 0이고 리스트가 [-1,1,-1,1]로 되어있을 경우 해당 조건문을 넣지 않으면 0과 1 인덱스만 확인하기 때문
3. 공집합까지 계산하는 것을 고려하여 S가 0인 경우 answer에 -1을 해줄 것.
    ex) S가 0인 경우 리스트 내의 모든 숫자를 더하지 않고 depth==N이면서 더해준 값(사실 안더해준거지만)이 0일 경우가 있기 때문

 

import sys

N,S=map(int, sys.stdin.readline().split())
sequence=list(map(int, sys.stdin.readline().split()))

answer=0
def BFS(depth, number):
    global answer
    if depth==N:
        if number==S:
            answer+=1
        return 

    BFS(depth+1, number)
    BFS(depth+1, number+sequence[depth])
    
BFS(0,0)
if S==0 : answer-=1
print(answer)