책너두 - 알고리즘 챌린지[16/20]

오늘의 문제 : 부분수열의 합

오늘의 문제는 개발자라면 꼭 풀어야하는 문제라고 방장님이 보내주셨다.

브루트포스로 풀면 시간 초과가 나지 않을까 걱정했는데, 다행히 주어진 값의 범위를 보니 그럴 것 같지는 않았다.

1 ≤ N ≤ 20, |S| ≤ 1,000,000

재귀를 통해, 리스트를 돌면서 값이 들어간 경우와 들어가지 않은 경우로 구분해서, 수열의 합이 S가 된다면 cnt를 +1 해주는 방식으로 풀 수 있었다.

import sys

def dfs(idx, _sum) :
    global cnt

    if idx == n :
        return
    _sum += nums[idx]

    if _sum == s :
        cnt += 1

    dfs(idx+1, _sum)
    dfs(idx+1, _sum - nums[idx])


n, s = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))
cnt = 0

dfs(0, 0)
print(cnt)