[Python][백준 1182] 부분수열의 합

문제

https://www.acmicpc.net/problem/1182

이 문제는 부분 수열의 합이 S와 같아질 때의 횟수를 구하는 문제로, 백트래킹 알고리즘을 활용하여 풀 수 있다.

소스코드

from sys import stdin 
input = stdin.readline

N,S = map(int,input().split())
num = list(map(int,input().split()))

cnt = 0 # 부분수열의 합이 S 인 경우 cnt += 1
ans = [] # 재귀함수에서 선택한 원소들을 저장하는 용도의 리스트 

def solve(start): #start : 현재 선택할 원소의 인덱스 
    global cnt
    if sum(ans) == S and len(ans) > 0:
        cnt += 1

    for i in range(start,N): # 반복문을 통해 현재 인덱스부터 마지막 인덱스까지의 원소를 하나씩 선택
        ans.append(num[i]) # 해당 원소를 ans 리스트에 추가한 후, solve 함수를 재귀적으로 호출
        solve(i+1) # start 인덱스를 i+1로 설정하여 다음 인덱스부터 원소를 선택하는 이유는 중복을 피하기 위해서임
        ans.pop() # 재귀 호출이 끝난 후에는 ans 리스트에서 마지막으로 선택한 원소를 제거

solve(0)
print(cnt)

자세한 풀이

입력으로 다음과 같이 들어왔을 때 동작 과정

5 0
-7 -3 -2 5 8

1.초기화 및 solve(0) 호출:

cnt = 0: 부분수열의 합이 0인 경우의 수를 저장할 변수
ans = []: 선택한 원소를 저장할 리스트
solve(0)을 호출하여 재귀 함수 시작

2.재귀 함수 solve 호출 (start = 0):

sum(ans) == S를 만족하는 경우:
ans 리스트의 합이 0이 되는 경우이므로 cnt 값을 1 증가시킴
반복문에서 start = 0일 때 i가 0, 1, 2, 3, 4까지 순회:

3.첫 번째 반복 (i = 0):

ans.append(num[0]): -7을 ans 리스트에 추가
재귀 함수 solve 호출 (start = 1):
sum(ans) == S를 만족하지 않으므로 아무 동작 없음
반복문 종료 후 ans.pop(): -7을 ans 리스트에서 제거

2.두 번째 반복 (i = 1):

ans.append(num[1]): -3을 ans 리스트에 추가
재귀 함수 solve 호출 (start = 2):
sum(ans) == S를 만족하지 않으므로 아무 동작 없음
반복문 종료 후 ans.pop(): -3을 ans 리스트에서 제거

3.세 번째 반복 (i = 2):

ans.append(num[2]): -2를 ans 리스트에 추가
재귀 함수 solve 호출 (start = 3):
sum(ans) == S를 만족하지 않으므로 아무 동작 없음
반복문 종료 후 ans.pop(): -2를 ans 리스트에서 제거

4.네 번째 반복 (i = 3):

ans.append(num[3]): 5를 ans 리스트에 추가
재귀 함수 solve 호출 (start = 4):
sum(ans) == S를 만족하지 않으므로 아무 동작 없음
반복문 종료 후 ans.pop(): 5를 ans 리스트에서 제거

5.다섯 번째 반복 (i = 4):

ans.append(num[4]): 8을 ans 리스트에 추가
재귀 함수 solve 호출 (start = 5):
sum(ans) == S를 만족하지 않으므로 아무 동작 없음
반복문 종료 후 ans.pop(): 8을 ans