SW Expert Academy

D3 2817번 부분 수열의 합(python)

문제

풀이과정

조합 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]))