[백준] [파이썬] [백트래킹] [DFS] 1182번: 부분수열의 합

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

1182번: 부분수열의 합 문제 보러 가기

문제

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

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

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

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

---

 

몇개를 뽑는지 나와 있지 않다. N개의 수중 몇개 짜리 부분 수열인지 안 정해져 있기 때문에 1개짜리 부분집합, 2개짜리 부분집합, 3개짜리 부분집합... 이렇게 해서 집합의 합이 원하는 S가 되는지 확인해보면 된다.

다시 말해, 1개 뽑는거부터 N개 뽑는거 까지 반복하면 된다.

 

---

 

정답

 

import sys 

def DFS(L,s):
    global cnt
    if L==c:				# c개 뽑는거
        if sum(res)==S:
            cnt+=1
    else:
        for i in range(s,N):
            if visited[i]==0:		# 중복을 피하기위해
                visited[i]=1
                res[L]=nums[i]
                DFS(L+1,i+1)		# 중복을 피하며 나보다 뒤에 있는 항을 가져오는 부분수열
                visited[i]=0


if __name__=="__main__":
    N,S=map(int, input().split())
    nums=list(map(int, input().split()))
    cnt=0
    for c in range(1,N+1):		# 1개 뽑는거부터 N개 뽑는거까지
        res=[0]*c
        visited=[0]*N
        DFS(0,0)
    print(cnt)

 

---