백준,부분 수열의 합,1182

[유형]

백트래킹

 

[문제링크]

https://www.acmicpc.net/problem/1182

 

[요약]

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

 

[문제풀이]

백트래킹 문제로 ans를 출력하면 다음과 같다.

import sys

from itertools import permutations

def input():
    return sys.stdin.readline().rstrip()

def dfs(start):
    global cnt
    if sum(ans) == s and len(ans) >0:
        cnt+=1

    for i in range(start,n):
        ans.append(num_list[i])
        dfs(i+1)
        ans.pop()


n,s = map(int,input().split())
num_list = list(map(int,input().split()))
ans = []
cnt = 0

dfs(0)
print(cnt)