[백준] 1182 - 부분수열의 합 [Python(파이썬)]

문제

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

문제가 약간 이상하다. 당연히 경우의 수를 구하는 것이기 때문에 중복을 제거해줘야 한다고 생각했는데 중복을 제거하면 틀리게 나온다.

 

조합을 사용하거나 재귀를 이용하여 풀 수 있다. 조합을 사용하는 방법이 더 직관적이지만, 재귀를 이용하는 방법이 메모리나 속도면에서 효율적이다.

 

리스트의 첫번째 인덱스에서 시작해서 해당 요소를 건너뛰고 다음 인덱스로 가거나 해당 요소를 포함하고 다음 인덱스로 가는 식으로 재귀함수를 구현할 수 있다.

 

코드

조합

import sys
from itertools import combinations

n, s = map(int, sys.stdin.readline().split())
nums = [int(x) for x in sys.stdin.readline().split()]

cnt = 0

for i in range(1, n+1):
    combis = list(combinations(nums, i))
    for combi in combis:
        if sum(combi) == s:
            cnt += 1

print(cnt)

재귀

import sys

n, s = map(int, sys.stdin.readline().split())
nums = [int(x) for x in sys.stdin.readline().split()]

cnt = 0

def solve(idx, total):
    global cnt
    if idx >= n:
        return   
    
    total += nums[idx]
    if total == s:
        cnt += 1

    solve(idx+1, total)
    solve(idx+1, total-nums[idx])

solve(0, 0)
print(cnt)