[백준/BOJ] - 1182번 python 풀이 - backtracking

---

백트래킹이란 쉽게 말해 가지 치기를 하는 알고리즘.

해당 문제는 depth를 기준으로 depth가 주어진 정수의 개수를 넘어 갔을 경우

더이상 탐색이 불가하므로 장치를 걸어놓아 함수를 리턴시켜 문제를 해결하는 백트래킹 문제이다.

 

트리를 생각해보면 맨처음 depth 0부터 주어진 정수의 개수-1 만큼의 depth가 허용 범위이다.

즉, 주어진 정수의 개수 = depth가 될 경우 문제가 생긴다는 것.

이를 중점으로 해결해보자.

 

---

import sys
input = sys.stdin.readline

m,n = map(int,input().split()) #정수 개수, 원하는 합
arr = list(map(int,input().split()))
ans = 0
def recur(depth,T_sum):
    global ans
    if depth ==  m:
        return
    val = arr[depth]
    T_sum += val
    if T_sum == n:
        ans+=1
    recur(depth+1,T_sum) #값을 더한 상태로 다음 함수에 넘기기
    recur(depth + 1, T_sum-val) #값을 더한 것을 도로 빼는 경우의 수

recur(0,0)
print(ans)