백준 / 부분수열의 합 / 1182번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 부분수열의 합 / 1182번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/1182

 

문제 설명

---

나의 풀이

# 전역변수
count = 0

def dfs(index, current_sum, s, sequence):
    global count

    if index >= len(sequence):
        return

    # 현재 원소를 포함하는 경우
    current_sum += sequence[index]
    if current_sum == s:
        count += 1  # 부분수열의 합이 S이면 카운트 증가

    # 다음 원소 탐색 (현재 원소 포함한 경우)
    dfs(index + 1, current_sum, s, sequence)

    # 현재 원소를 포함하지 않는 경우 (백트래킹)
    dfs(index + 1, current_sum - sequence[index], s, sequence)


def main():
    global count
    n, s = map(int, input().split())  # N, S 입력
    sequence = list(map(int, input().split()))  # 수열 입력

    # DFS 실행
    dfs(0, 0, s, sequence)

    print(count)


main()

---

※ 알아야 할 것

백트래킹을 이용한 문제이다!

소요 시간: 21:12

사유: 많이 풀어봤던 문제의 유형이라 비교적 쉽게 넘어갔다.