[백준/파이썬] 1182번 부분수열의 합 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1182번 부분수열의 합
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정수 수열에서 공집합이 아닌 부분수열의 합이 S가 되는 경우의 수를 구하는 문제입니다.

코드

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

cnt = 0

def sumOfSubset(index, sos):
    if(index >= n):
        return

    global cnt
    sos += nums[index]
    cnt += 1 if sos == s else 0
    
    sumOfSubset(index+1, sos)
    sumOfSubset(index+1, sos-nums[index])

sumOfSubset(0, 0)
print(cnt)

설명

각 인덱스에서 현재 원소를 선택/비선택하는 재귀 분기를 만듭니다.

• 선택: 합(sos)에 현재 값을 더함
• 비선택: 더했던 값을 다시 빼고 다음 인덱스로 진행

재귀 탐색 중 합이 S가 되는 경우를 카운트해 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---