백준 1182 파이썬 (부분수열의 합)

문제 : https://www.acmicpc.net/problem/1182
알고리즘 분류 : BackTracking

💻 Code

N, S = map(int, input().split())
num = list(map(int, input().split()))
cnt = 0
ans = []

def solve(start):
    global cnt
    if sum(ans) == S and len(ans) > 0:
        cnt += 1

    for i in range(start, N):
        ans.append(num[i])
        solve(i+1)
        ans.pop()

solve(0)
print(cnt)

• 원소끼리 떨어져 있는 경우도 부분수열이라서 더 어려웠다

• 전체 흐름을 이해하기가 너무 어려워서 출력해봤다.
  

백트래킹 풀면서 새삼 멍청하다고 느끼는중 진짜 포기하고 싶ㄷ ㅏ...