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

1182번: 부분수열의 합

n, s = map(int,input().split())

# N개의 정수로 이루어진 수열, 부분수열의 원소를 다 더한 값이 S가 되는 경우의 수

data = list(map(int,input().split()))

count = 0

visited = [False]*n

def dfs(total,index,depth):
    global count

    if total == s and depth != 0:
        count += 1

    for i in range(index,n):
        if not visited[i]:
            visited[i] = True
            dfs(total + data[i], i,depth+1)
            visited[i] = False

dfs(0,0,0)

print(count)

이번 문제는 N개의 정수로 이루어진 수열에서 '부분수열 중 원소의 합이 S가 되는 경우의 수'를 구하는 문제이다.

 

일단 부분수열을 만들어주기 위해 dfs를 사용했고, 처음에는 for문으로 경우의 수를 탐색할 때 모든 원소를 다 고려했었는데 이렇게 완전 탐색을 하게 되면 중복되는 경우(ex. '-3, -2, 5', '5, -3, -2')가 발생하여 경우의 수가 중복되는 현상(순열)이 발생했다. 🚨

 

따라서 index를 인수로 전달하여 index부터 탐색함으로써 이미 경우의 수를 따진 이전 원소들은 탐색하지 않게 되었다.(조합, Backtracking)

 

완전탐색과 백트래킹 알고리즘의 차이점을 파악할 수 있었던 좋은 문제였다 :)