조합 combinations
를 모두 구해 문제를 해결할 경우 시간 초과
재귀함수를 통해 완전 탐색
현재 인덱스에 해당하는 원소를 포함하는 경우, 그렇지 않은 경우
각각의 재귀함수 호출을 통해 확인
재귀함수의 종료 조건과 호출 형태 설계하기
T = int(input())
result = []
def solve(idx, curr_sum):
global count
temp = curr_sum + seq[idx]
if temp == k: #조건과 일치할 경우
count += 1
return
if idx == n: #끝까지 탐색한 경우
if temp == k: # 조건과 일치할 경우
count += 1
return
if temp > k: #정해진 k 보다 큰 경우 추가되는 조합을 찾을 필요가 없다
return
solve(idx + 1, curr_sum) #현재 인덱스의 숫자를 선택하지 않은 경우
solve(idx + 1, temp) #현재 인덱스의 숫자를 선택하여 합한 경우
for t in range(T):
n, k = map(int, input().split())
seq = list(map(int, input().split()))
count = 0
solve(0, 0) #0번째 원소부터, 현재 합은 0
result.append(count)
for t in range(T):
print("#{} {}".format((t + 1), result[t]))