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

1182번: 부분수열의 합

해당 문제는 완전탐색 문제로 수열의 개수 N이 주어졌을때 특정 위치가 있는경우와 없는경우 의 조합으로 이야기 할 수 있습니다. 따라서 시간복잡도는 O(2^n) 입니다. 깊이우선탐색으로 해당 조합을 생성합니다. 조합을 만들어가면서 누적합이 S인 경우를 가중치에 추가합니다.

import sys
input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))

cnt = 0
def solve(queue, idx):
    global cnt
    if queue:
        if sum(queue) == S:
            cnt += 1

    for i in range(idx, N):
        queue.append(arr[i])
        solve(queue, i+1)
        queue.pop()

solve([], 0)
print(cnt)

<aside> 💡 처음에 제가 잘못생각했던 부분은 20! 경우의 수라고 생각을 했었습니다. 그래서 다른 알고리즘으로 풀으려 접근 하였으나 찾지 못하여 풀이법을 확인해본결과 부분수열은 특정위치의 값이 있는경우와 없는 경우의 경우의 수 이기때문에 위와 같이 시간복잡도를 생각 할 수 있습니다.

</aside>