[알고리즘/Python] BOJ 1182 부분수열의 합

👉 1182 부분수열의 합

1182번: 부분수열의 합

👀 접근 :: 

• N개의 정수로 이루어진 수열의 부분 수열 중에서 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다. 
• 백트래킹 문제임을 알고 접근했기에 DFS 로 깊이 탐색을 하면서 조건을 체크했다. 

백트래킹? 트리 구조를 기반으로, DFS 로 깊이 탐색하면서 각 루트에 대해 조건을 체크한다. 만약, 해당 트리에 조건이 맞지 않으면 해당 트리 탐색을 종료한다.

✔︎ 문제 풀이 방법

• 부분 수열은 1차원 배열로 나타낼 수 있다.
• 1차원 배열에서 인덱스를 증가시키면서 부분 수열의 합을 계산했다.
• 부분 수열의 합이 S가 되는 경우, 정답의 개수를 증가시켰다.

 

✔︎ 실수했던 부분

1. 반복하는 인덱스가 N이 되었을 때 부분 수열의 합을 계산하면 안된다.

마지막 인덱스에 도달하지 않아도 "부분 수열의 합" 이므로 정답에 해당할 수 있다.

 

2. "부분 수열의 합"이 S가 되었다고 탐색을 종료하면 안된다.

다음 경우에서 정답이 될 수 있는 부분 수열은 [3], [3, -3, 3], [3] 으로 세가지 경우가 나온다.

0번째 인덱스에서 합이 3이 되었다고 탐색을 종료하게되면 전체 집합의 경우는 포함되지 못한다. (음수가 조건에 있기 때문에 해당 경우를 고려해야한다.)

3 3
3 -3 3

 

👩‍💻 Python 코드

from sys import stdin
input = stdin.readline

n, s = map(int, input().split())
nums = list(map(int, input().split()))
result = 0

def dfs(i, graph, total):
    global result, s, n
    if total == s:
        result += 1
    
    # graph (부분수열) 만들기
    for j in range(i+1, n):
        dfs(j, graph, total + graph[j])

for i in range(0, n):
    dfs(i, nums, nums[i])

print(result)