[baekjoon] 백준 1182번(파이썬): 부분수열의 합

문제

1182번: 부분수열의 합

알고리즘

- 재귀와 백트래킹을 통해 문제를 수행한다.

- 백트래킹 함수를 만들어 매개변수를 idx와 수열의 합으로 선언한다.

- 현재 idx가 정수의 개수보다 크면 리턴한다.

- 수열에 현재 idx 정수를 더한다.

- 현재 수열의 합이 s라면 카운트한다.

- 현재 idx 정수를 더한 값을 백트래킹 함수에 넣어 재귀적으로 탐색한다.

- 위 탐색이 끝난 후 현재 idx 정수를 더하지 않은 값을 백트래킹으로 재귀적으로 다시 탐색한다.

코드

import sys


# 백트래킹 함수
def back_tracking(idx, res):
    global cnt

    # 현재 idx가 정수의 개수보다 크면 리턴
    if idx >= n:
        return

    # 수열에 현재 idx 정수를 더한다.
    res += k[idx]

    # 현재 수열이 s라면 카운트
    if res == s:
        cnt += 1

    back_tracking(idx + 1, res) # 현재 idx 정수를 더한 것
    back_tracking(idx + 1, res - k[idx]) # 현재 idx 정수를 더하지 않은 것(백트래킹)


n, s = map(int, sys.stdin.readline().split())
k = list(map(int, sys.stdin.readline().split()))
cnt = 0

back_tracking(0, 0)
print(cnt)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법