[백준] 1182_부분수열의 합 (Python)

1182_부분수열의 합 (Python)

0. 출처

• 유형 : 백트래킹, 브루트포스 (silver 2)
• 링크 : 1182번: 부분수열의 합

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 부분 수열을 구한다.
>> 부분 수열의 합을 구하고 만족하는 부분수열을 카운트한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5 0
-7 -3 -2 5 8

- 예제 출력 1 -
1

(3) 코드

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

result = []

def iterative_dfs(index, path):
    # 매번 결과 추가
    result.append(path)

    for i in range(index, len(nums)):
        path = path+[nums[i]]
        iterative_dfs(i+1, path)

iterative_dfs(0, [])

cnt = 0

for answer in result:
    if answer != [] and sum(answer) == s:
        # print(answer)
        cnt += 1

print(cnt)

(4) 정리

(5) 참고

알고리즘 인터뷰 Q37. 부분집합 문제를 참고하면 좋습니다.