[백준] 1182 : 부분 수열의 합 / python

1. 문제 설명

1182번: 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때,

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

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)

둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

2. 풀이 전 계획과 생각

부분수열의 갯수를 구한다.

모든 부분 수열을 따질 경우,

시간 복잡도는 2^20 - 1 = 약 10^6

완전 탐색으로 구할 수 있다.

 

합이 S가 되는 모든 경우의 수를 다 따진다.

합이 S가 되면 count 증가시킨다.

 

3. 풀이 - 조합

from itertools import combinations

N, S = map(int, input().split())
arr = list(map(int, input().split()))
count = 0

for num in range(1, N+1):
    for case in list(combinations(arr, num)):
        if sum(case) == S:
            count += 1

print(count)

 

4. 풀이 - 재귀로도 풀어보기

⇒ 해당 원소를 순회해서 고를지 안고를지 결정한다.

 

이를 위해, 매 함수마다 해당 원소를 부분 수열에 포함할지 말지 결정하는 인덱스와

현재까지의 부분 수열의 합을 체크해줘야 한다.

⇒ go(index, sum)

 

또한 합을 찾았다고 해도 종료해주면 안된다. 뒤의 원소까지 포함한 합을 구해도 답이 되는 경우가 있다.

종료조건은 index == 배열의 size다.

⇒ 정답을 찾은 경우

• index == N and sum == M
• (있고 없는 경우를 다따지기 위해 재귀를 2번 호출하니 index가 N까지 가고난 뒤, count 해야 한다.)

⇒ 불가능한 경우

• index == N and sum ≠ M

⇒ 다음 경우

• index번째 부분수열에 추가 : go(index + 1, sum + arr[i])
• index번째 부분수열에 추가하지 않음 : go(index + 1, sum)

 

🤔  앗! 부분 수열의 크기가 양수라는 조건이 있으니,

전체에서 모두 포함하지 않는 경우는 빼주자.

전체에서 모두 포함하지 않는 경우가 정답이 될 때는 S가 0일 때다.

 

N, S = map(int, input().split())
arr = list(map(int, input().split()))
count = 0

def go(index, sum):
    global count
    if index == N :
        if sum == S:    count += 1
        return

    go(index + 1, sum + arr[index])
    go(index + 1, sum)

go(0, 0)
if S == 0:
    count -= 1
print(count)