2817. 부분 수열의 합 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

def dfs(length,lst):
    global cnt
    if sum(lst)>K:
        return
    if sum(lst)==K:
        cnt+=1
        return
    if length==N:
        return
    dfs(length+1,lst+[N_list[length]])
    dfs(length+1,lst)
            
T = int(input())

for test_case in range(1, T + 1):
    N,K=map(int,input().split())
    N_list=list(map(int,input().split()))
    cnt=0
    dfs(0,[])
    print(f'#{test_case} {cnt}')

• N개의 숫자를 선택할지 안할지를 백트래킹으로 구현하였다.
• 만약 lst의 모든 합이 K를 넘어가면 그냥 return, K라면 cnt+=1 후 return, 마지막으로 length 즉 N개의 숫자에 대해 모두 선택을 하였다면 return을 해주었다.