소스코드
import sys
input = sys.stdin.readline
N,S = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
def recursive_solve(depth, total):
if depth == N:
return 1 if total == S else 0
return recursive_solve(depth+1, total + arr[depth]) + recursive_solve(depth+1, total)
result = recursive_solve(0, 0)
if S == 0:
result -= 1
print(result)
Python
복사
풀이
•
수열의 원소들의 합이 S가 되는 경우의 수 → 모든 경우의 수를 고려해야겠다고 생각했습니다
•
입력에 대해서, 각 원소들은 포함이 될 수도 안 될 수도 있습니다. 이런 방식으로 재귀함수를 2개씩 만들어내고 값을 합산하는 식으로 함수를 정의했습니다.
◦
그려놓고 보니 트리 형태더라구요. 그래서 depth를 설정해서 N까지 도달하면 현재까지의 총합이 S와 일치하는지 여부를 확인해 0 또는 1을 반환하도록 했습니다.