[Python] SWEA 2817번 부분 수열의 합

문제

SW Expert Academy

문제 풀이

• 재귀적으로 리스트의 각 값을 더해가면서 k값이 됐을 때 카운트 해 준다.
• 카운트 한 값을 형식에 맞게 출력한다.

코드

def find_k_val(index, num):
    # 더한 값이 k인 횟수를 세는 전역변수
    global cnt

    # 재귀 종료조건 (인덱스 끝까지 탐색을 마친경우, 더한 값이 k인 경우)
    if num == k:
        cnt += 1
        return

    if index == n:
        return

    # 값을 더하기 위해 현재 인덱스의 값 임시변수에 할당
    tmp = array[index]

    find_k_val(index+1, num + tmp) # 현재 값에 현재 인덱스의 값을 더하는 경우 탐색
    find_k_val(index+1,num) # 현재 값에 현재 인덱스의 값을 더하지 않는 경우 탐색


t = int(input())
for tc in range(t):
    # 문자 수 n개 중 합이 k값인 경우의 수 구하기
    n,k = map(int,input().split())
    array = list(map(int,input().split()))

    # 탐색 위한 전역변수 선언
    cnt = 0

    # 탐색하기 위한 인덱스 번호와 현재 값 넘기기
    find_k_val(0,0)

    # 탐색 마친 후 전역변수로 선언했던 카운트 값 형식에 맞게 출력
    print(f'#{tc + 1}',cnt)