백준 - 1182 부분수열의 합

💡문제 분석 요약

• 두번째 줄에 입력된 값들의 합 중 S 와 같은 값이 있다면 더하여, 합의 결과가 S와 같은 값이 몇개가 있는지 알아내는 문제.

💡알고리즘 설계

DFS에서 조금 응용하여 만약 반복문에서 돌고 있는 리스트의 인덱스 번호가 N보다 큰 값이라면 종료.

💡변경한 코드

def dfs(i, SUM):
  global cnt
  if i >= N:
      return
  SUM += n_list[i]
  if SUM == S :
    cnt += 1
  dfs(i+1, SUM-n_list[i])
  dfs(i+1, SUM)


N,S = map(int, input().split())
n_list = list(map(int, input().split()))
cnt = 0
dfs(0,0) #index 번호도 처음은 0이고, 처음 더한 값도 0이기 때문
print(cnt)

💡시간복잡도

💡 틀린 이유

재귀함수로 처음 dfs 를 다시 호출할 때 어떻게 해야할지 막막했다.

💡 틀린 부분 수정 or 다른 풀이

합을 다시 구해야하기 때문에 SUM-n_list[i]를 추가함

💡 느낀점 or 기억할정보

백트래킹과 DFS의 차이점은 알았다. 하지만 백트래킹을 DFS와 다르게 어느시점에 구현해야하는지 잘 모르겠다.
DFS로 구현했다가 시간 초과가 나면 바로 BFS 로 해보고 BFS로 해도 시간초과 오류가 뜨면 백트래킹으로 해야하는 걸까 ?
ㅜㅜ 어렵다