[SWEA] 부분 수열의 합 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB 

SW Expert Academy

부분 수열의 합 문제

수열의 부분 집합의 합을 구하고 그 합이 K가 되도록 만족하는 합의 개수를 구하는 문제

백트래킹을 이용하여 풀 수 있다.

⚙️내가 푼 정답 코드

def backtracking(a,b):
    global result
    if a == N: # 수열 다 뒤졌으면
        return # 끝
    b += x[a] # 현재 인덱스 까지 합
    if b == K: # 합이 K면
        result +=1 # 횟수 +=1 하고
    backtracking(a+1,b) #인덱스 1개씨 늘려서 찾아보기
    backtracking(a+1,b-x[a])

T = int(input())
for case in range(1,T+1):
    N, K = map(int, input().split())
    x = list(map(int,input().split()))
    result = 0
    backtracking(0,0)
    print(f'#{case} {result}')

📌문제 접근 포인트

1. 부분 수열의 합을 구해주기 위한 방법으로 itertools를 사용하는 방법도 있겠지만, 백트래킹을 구현해서도 해결 할 수 있다
2. 백트래킹을 구현해, 각 부분 집합을 구해주고, 합을 구한 뒤 비교를 해주면 된다.
3. 백트래킹 개념을 이용하면 비교적 어렵지 않게 구현 할 수 있다.