[비타알고2] 환상의 조합 python

문제

최고의 팀을 짜는 방법은 팀원의 능력치의 합이 S가 되게 하는 것이다. 예를 들어 S=5일 때, 사람들의 능력치가 각각 -3, 0, -1, 8, 9라고 해보자. 그렇다면 홍현이를 포함하여 만들 수 있는 최고의 팀은 (-3,-8), (-3,0,8), (-3,-1,9), (-3,0,-1,9)

 

입력

첫 번째 줄에는 사람의 수 N과 최고의 팀을 만들기 위한 수 S가 주어짐. (5<=N<=20), (절댓값S <=10000)

두 번째 줄에는 각 사람의 수치화된 능력 a가 공백으로 구분되어 주어짐. (절댓값a <= 10000)

이 때 첫 번째로 주어지는 능력은 홍현이의 능력.

ex)

5 5

-3 0 -1 8 9

출력

최고의 팀을 만들 수 있는 경우의 수를 출력. 팀의 팀원은 최소 1명 이상이어야 한다. (홍현 혼자서도 팀 구성 가능)

ex)

4

 

풀이

n, s = map(int, input().split())
arr = list(map(int, input().split()))

cnt = 0
score = arr[0]

def makeTeam(idx, score):
	global cnt
	if idx == n: #n-1번 idx까지 돌고 n번 idx가 되었을 때 return
		cnt += (score==s)
		return
	makeTeam(idx+1, score) #현재 idx의 value 포함하지 않고 다음으로 넘어가기
	makeTeam(idx+1, score + arr[idx]) #현재 idx의 value 포함하고 다음으로 넘어가기

makeTeam(1, score) #0(홍현)은 무조건 포함이므로 idx1 부터 시작
print(cnt)