서론

브루트포스, 백트래킹 문제입니다.
부분수열, 즉 이어진 수들로만 합을 구해야 하기 때문에 백트래킹을 이용하여 풀었습니다.

난이도

실버 2

---

문제

조건

시간 제한	메모리 제한
2 초	256 MB

---

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

---

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

예시

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

---

풀이

기본적인 백트래킹으로 풀 수 있는 문제입니다.
현재 위치의 수를 더함, 백트래킹을 수행, 현재 위치의 수를 뺌 -> 이 과정의 반복입니다.

예제의 경우,
-7
-7 - 3
-7 - 3 - 2
-7 - 3 - 2 + 5
-7 - 3 - 2 + 5 + 8
-3 - 2
-3 -2 + 5 -> 합이 0이므로 ans + 1
이후 생략

위와 같은 과정을 반복합니다.
이 과정이 문제에서 요구하는 부분 수열의 합을 찾는 것입니다. (이어진 수들로만 합을 구하기 때문)

코드

import sys
input = sys.stdin.readline

def dfs(idx, total):		# 백트래킹, idx: 현재 인덱스, total: 합
    if idx == n:			# 마지막 인덱스면 종료
        return
    
    for i in range(idx, n):	# 현재 인덱스부터 n까지 반복
        total += nums[i]	# 현재 위치의 수를 더함
        if total == s:		# 더한 수가 s와 같다면 정답 +1
            global ans
            ans += 1

        dfs(i + 1, total)	# 인덱스를 증가시키며 백트래킹 호출
        total -= nums[i]	# 현재 위치의 수를 뺌

n, s = map(int, input().split())
nums = list(map(int, input().split()))
ans = 0

dfs(0, 0)

print(ans)

실행 결과