BOJ 1182번: 부분수열의 합

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

1182번: 부분수열의 합

이전에 풀었던 문제인데, 백트레킹 문제를 너무 오랜만에 풀어서 감이 잘 오지 않았다. 이제는 주먹구구식으로 풀기보다 유형별로 정리해서 공부를 제대로 해야겠다..

재귀를 이용해서 풀 수 있었다.

 

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N, S = map(int, input().split())
num = list(map(int, input().split()))
cnt = 0

def solve(i, total):
    global cnt
    if (i == N):
        if (total == S):
            cnt += 1
        return
    solve(i+1, total)
    solve(i+1, total+num[i])
solve(0, 0)
if (S==0):
    cnt -= 1
print(cnt)