백준 1182번(부분 수열의 합) 파이썬

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

1182번: 부분수열의 합

한동안 너무 바빠 블로그에 글을 쓸 시간이 없었다..(변명이지만..) 코딩테스트 준비, 개인 프로젝트, 학교 공부 등 할게 너무 많았다. 알고리즘 문제는 가끔씩 계속 풀었지만 블로그에 글을 쓰진 못했다. 할게 너무 많아서 생각 조차 안났다..

그래서 오랜만에 글을 쓰게 되었다. 앞으로도 전과 비해선 글을 쓰는 빈도가 많을 거 같진 않다. 하지만 일주일에 2번이라도 글을 써보도록 하겠다. 

 

이번 문제는 백트래킹 문제이다. 그다지 크게 어려운 문제는 아니니 코드에 있는 주석들을 보며 이해하면 된다.

물론 N과M 같은 문제들을 푼 사람들에게만 해당 되는 문제이다. 처음 접하는 사람들은 백트래킹이 뭔지 공부부터 하고 코드를 보길 추천한다!!

import sys
input = sys.stdin.readline

n,s = map(int,input().split())
array = list(map(int,input().split()))
ans = []
total = 0 

def dfs(start):
    global total
    if sum(ans) == s and len(ans)>0: # 합이 s와 같고 길이는 0보다 커야한다.
        total+=1 
    for i in range(start,n): # 모든 부분 수열을 검사해줄 for문이다.
        ans.append(array[i])
        dfs(i+1) # 다시 다음 위치부터 또 다른 부분수열을 검사한다.
        ans.pop() # 검사가 끝나고 더이상 넣을게 없다면 pop()시켜준다

dfs(0)
print(total)