[BOJ] 백준 1182번 부분수열의 합 (Python)

문제

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

풀이

def dfs(_idx, _sum):
    global n, s, arr
    _num = 0					# 합이 s인 부분수열의 개수
    if _idx == n:				# arr 벗어남
        return 0
    if _sum + arr[_idx] == s:			# 이번 숫자를 더했을 때 s와 같다면
        _num += 1				# _num을 1 높임

    # 백트래킹
    _num += dfs(_idx + 1, _sum)			# 이번 숫자 포함 X
    _num += dfs(_idx + 1, _sum + arr[_idx])	# 이번 숫자 포함 O

    return _num					# 백트래킹을 통해 얻은 값을 리턴


n, s = map(int, input().split())		# 입력
arr = list(map(int, input().split()))		# 숫자 입력

print(dfs(0, 0))

예제에서 입력 1처럼 [-7, -3, -2, 5, 8]이 입력되었다고 했을 때, 이 리스트에서 순서대로 하나씩 포함하는 경우, 포함하지 않은 경우를 따져보고 조건이 만족하면 _num을 1 올려주는 방식으로 했다.
예를 들면

idx	0	1	2	3	4
	X	X	X	X	X
	X	X	X	X	O
	X	X	X	O	X
	X	X	X	O	O
	X	X	O	X	X
	X	X	O	X	O

...

이 순서로 포함 여부를 하나씩 해보고 그 더한 값을 비교해보는 것이다.