백준 1182 부분수열의 합

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

1182번: 부분수열의 합

📌 해결순서

모든 부분수열의 합을 구해야 하므로, 완탐으로 구해야함을 알수 있고 더하는 숫자들의 중복이 있으므로 백트래킹으로 하나씩 제거하고 다음 수를 추가해주는 식으로 풀어야한다고 생각했다.

 

1. 부분수열의 크기가 양수여야 하므로 부분수열을 담는 배열의 길이가 1 이상인 경우에만 합을 구한다

2. 항상 부분수열을 담는 배열에 저장되는 숫자들의 원래 인덱스 값은 오름차순이다.

예제의 수열 [-7 , -3, -2, 5, 8] 에서 (-7 + -3 + -2) == (-2 + -3 + -7) 이다. 따라서 1번만 합을 구하면 되기 때문에 인덱스 값이 오름차순이 되는 경우만 탐색한다

3. 부분 수열에 같은값이 있을수 있기 때문에, 인덱스를 사용하여 비교해서 만족하면 탐색을 계속 진행한다

 

📌 코드

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
lst = list(map(int, input().split()))
cnt = 0
nums = []


def dfs(x):
    global cnt
    sum = 0
    # 부분수열의 길이가 0이 아닌 경우에만 합을 구한다.
    if len(nums):
        for num in nums:
            sum += num
        if sum == s:
            cnt += 1

    for i in range(x, n):
        if lst[i] not in nums:
            nums.append(lst[i])
            dfs(i + 1)
            nums.pop()
        # 같은 값의 숫자가 이미 배열에 있더라도, 인덱스 값이 다르면 계속해서 탐색을 진행할 수 있도록 해준다.
        else:
            if nums.index(lst[i]) != i:
                nums.append(lst[i])
                dfs(i + 1)
                nums.pop()


dfs(0)
print(cnt)