[백준] 1182 - 부분수열의 합

문제

백준 1182번 부분수열의 합

문제 링크 : https://www.acmicpc.net/problem/1182

 

 

문제 풀이

목적 : 주어진 수열에서 어떤 부분수열의 합이 주어진 값 S와 일치하는 경우의 수를 구하는 것

부분수열은 연속되지 않아도 되기 때문에 부분수열의 모든 경우의 수를 탐색해야 한다. python itertools 패키지의 combinations 함수를 사용하여, 가장 큰 길이인 n부터 1까지의 경우에 대한 모든 부분수열 조합을 구한 후 합이 S와 같을 경우 answer 변수에 1을 추가한다.

 

코드

import sys
from itertools import combinations

input = sys.stdin.readline

n,s=map(int,input().split(' '))
lst=list(map(int,input().split(' ')))
answer=0
for size in range(n,0,-1):
  lsts= combinations(lst,size)
  for cand in lsts:
    if sum(cand)==s:
      answer+=1


print(answer)