백준 1182 [부분수열의 합]

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

# 백준 1182 부분수열의 합
N,S=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort() #정렬
ans=0 #정답
def search(start):
    global ans
    if s and sum(s)==S: #S와 부분집합의 합이 같다면
        ans+=1 #정답 갯수 증가
    for i in range(start,N):
        if visit[i]==0: #방문하지 않았다면
            s.append(lst[i]) #배열에 추가
            visit[i]=1 #방문확인
            search(i) #재귀적으로 탐색하되, 이전에 탐색한 인자는 탐색하지 않도록 start를 다음 for문의 시작 index로 설정
            visit[i]=0 #방문제거
            s.pop() #배열 삭제

s=[]
visit=[0 for _ in range(N)]
search(0)
print(ans)