[BOJ] 1182. 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

1. 해결방법

"""
1. 아이디어
- 입력받은 정수 S가 되기 위해 모든 경우의 수를 구함.
- 원소 하나씩 추가시키는 재귀랑 추가시키지 않는 재귀 두개를 구현해서 모든 경우의 수를 확인.
- 결과 리스트에 들어간 원소 값의 합들이 S가 되면 종료, print

2. 시간복잡도
- O(2^N)

3. 자료구조
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

입력 예제(1)

5 0
-7 -3 -2 5 8

출력 예제(1)

1

 

 

코드

import sys
input = sys.stdin.readline


n, s = map(int, input().split())
number = list(map(int, input().split()))

answer = 0

# recur
def recur(num, result):
    global answer

    # 재귀 종료 지점
    if num >= n:
        return

    # 재귀
    result += number[num]

    if result == s:
        answer += 1

    # 원소 값을 더한 재귀
    recur(num + 1, result)
    # 원소 값을 더하지 않은 재귀
    recur(num + 1, result - number[num])




# main
recur(0, 0)
print(answer)

 

평소 백트래킹 문제를 for문을 시작으로 재귀를 이용했다면, 이 문제는 for문을 사용하지 않고 원소 값을 더한 재귀와 더하지 않은 재귀를 나누어서 바로 해결할 수 있는 문제였다.

알고리즘 공부한지 일주일 조금 넘었지만 개인적으로 생각의 틀은 깬 문제였다.