[백준-파이썬] 1882-부분수열의 합

문제바로가기

import sys
sys.setrecursionlimit(10**6)

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

count = 0
combi = []

def back(n):
    global count
    if sum(combi) == S and len(combi)>0:
        # print(combi)
        count += 1
    
    for num in range(n, N):
        combi.append(numbers[num])
        back(num+1)
        # print(combi)
        combi.pop()
back(0)
print(count)

N과 M 문제 시리즈의 변형 같은 문제.
단지 멈추는 조건이 조합의 합이 S가 될 때로 바뀐 것 뿐이다. 한가지 간과한 것은 s가 0일 때 combi가 []인 경우도 포함되어서 count가 올라갔었다. 그래서 추가로 combi에 무조건 값이 있어야 한다는 조항을 추가했다.