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

문제

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

1182번: 부분수열의 합

 

 

백트래킹으로 접근 가능한 문제이다.

 

내가 백트래킹으로 풀려고 하는 문제의 특징은

 

1. 가능한 케이스들을 체크해주는 완전탐색의 성격

2. 특정 조건에서 더이상 체크해줄 필요가 없는 특징이 있다.

 

 

답이 되는 리스트들은 그 원소의 수가 다르거나, 같더라도 다른 원소를 포함하고 있을 것이기에, 현재의 index값을 가지고 포함시킬지, 포함시키지 않을 것인지를 체크해준다.

 

 

N, S = map(int, input().split())

arr = list(map(int, input().split()))
answer = 0
checker = set()


def dfs(idx, hap, cur):
    global answer
    if hap == S and len(cur) != 0 and tuple(cur) not in checker:
        answer += 1
        checker.add(tuple(cur))
    if idx >= N:
        return
        
    # 현재의 값이 들어가거나 안들어가거나
    dfs(idx + 1, hap, cur)
    dfs(idx + 1, hap + arr[idx], cur + [idx])

dfs(0, 0, [])
print(answer)