백준 | 부분수열의 합

백준 부분수열의 합 문제 풀이이다.

n개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 다 더한 값이 s가 되는 경우의 수를 구하는 프로그램을 작성하는 문제이다.

부분 수열이란 주어진 수열에서 원소들의 순서를 유지한 채, 일부 원소들을 골라낸 새로운 수열을 의미한다.

따라서 주어진 n개의 정수 중 1개, 2개, ..., n개를 고르는 조합 중 각 원소의 합이 s가 되는 것의 개수가 문제 조건을 만족하는 부분 수열의 개수가 된다.

이걸 코드로 구현하기 위해 itertools의 combinations 메서드를 썼다.

for 문을 통해 n개 중 i개를 선택하는 조합을 모두 구한 뒤, 각 케이스에 속한 원소의 합이 s가 되는 경우를 셌다.

코드(정답)는 다음과 같다.

import sys
from itertools import combinations


n, s = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))

cnt = 0
for i in range(1, n + 1):
    cases = list(combinations(numbers, i))
    for case in cases:
        if sum(case) == s:
            cnt += 1

print(cnt)