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

1182번: 부분수열의 합

POINT

Brute Force

• 모든 경우의 수를 탐색하여 정답을 찾는다.
• 전체 탐색을 사용한다. (순차 탐색, BFS, DFS 등)

Backtracking + DFS = Combinations

• 백트래킹과 DFS를 함께 사용하여 조합을 구현한다.

풀이

Python은 조합을 구현한 내장 함수가 있기 때문에 풀이도 내장함수를 사용한 방법과 아닌 방법으로 두 가지이다.

방법1️⃣

조합 내장 함수(combinations)를 사용한다.

from itertools import combinations

n, s = map(int, input().split())
data = list(map(int, input().split()))
answer = 0 # 합이 s인 부분 수열 개수

for i in range(1, n+1): # 1 ~ n개 뽑기
    cases = list(combinations(data, i))
    
    for case in cases:
    	# 합이 s이면 개수 증가
        if sum(case) == s:
            answer += 1
            
print(answer)

방법2️⃣

내장 함수를 사용하지 않고, 백트래킹 + DFS로 조합을 구현한다.

n, s = map(int, input().split())
data = list(map(int, input().split()))
answer = 0 # 합이 s인 부분 수열의 개수

def solve(cnt, _sum): # 뽑은 숫자 개수, 부분 수열의 합
    global answer
    
    # 배열 끝까지 도달하면 종료
    if cnt >= n:
        return
    
    _sum += data[cnt]
    
    # 주어진 s와 합이 동일하면 개수 증가
    if _sum == s:
        answer += 1
        
    solve(cnt + 1, _sum) # 자신을 합에 포함한 경우
    solve(cnt + 1, _sum - data[cnt]) # 자신을 합에 포함하지 않은 경우

solve(0, 0)
print(answer)