[백준] 1182 - 부분 수열 합 with.Python

💡문제 분석 요약

-- 문제 --

입력 : N개 정수, S 원소 더한 값(1 ≤ N ≤ 20, |S| ≤ 1,000,000)

크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수 구하기

💡알고리즘 설계

💡코드

💡시간복잡도

O(N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

(https://seongonion.tistory.com/98 풀이 참고하였습니다.)

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

def subset_sum(idx, sub_sum):
    global cnt

    if idx >= n:
        return

    sub_sum += arr[idx]

    if sub_sum == s:
        cnt += 1

    # 현재 arr[idx]를 선택한 경우의 가지
    subset_sum(idx+1, sub_sum)

    # 현재 arr[idx]를 선택하지 않은 경우의 가지
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)
print(cnt)

💡느낀점 or 기억 할 정보

처음 코테를 접하다보니 접근하는데 어려움을 느낌. -> 문제 많이 접해보기.
개념만 공부하지 말고 기본 구현한 코드 많이 접해보기.
subset_sum(idx + 1, sub_sum) : 다음 요소로 넘어가서 부분 수열을 계속 탐색하고 sub_sum에 누적된 값 사용
subset_sum(idx + 1, sub_sum - arr[idx]) : 현재 idx에 해당하는 요소를 선택하지 않고 다음 단계로 넘어가는 경우 처리