[백준] 1182 부분수열의 합

🌭 문제 설명

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

---

🍗 제한 사항

---

🎁 입출력 예시

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

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

---

😎 나의 풀이

N,S = map(int,input().split())
arr = list(map(int, input().split()))
count = 0

from itertools import combinations

for n in range(1, N+1): # 1부터 N까지 부분집합 탐색
  for s in combinations(arr,n): # 부분집합 탐색
    if sum(s) == S: # 부분집합의 합이 S면 
        count += 1 # count 추가
      
print(count)

1. 부분수열의 개수는 부분집합을 뽑는 문제라고 생각하면 된다.
2. 파이썬의 조합라이브러리인 combinations를 이용해서 1~N까지 탐색을 하고, 부분집합을 탐색해준다.
3. 부분집합의 합이 S와 같으면 count를 추가해서 개수를 세준다.

---

• 백트래킹 풀이도 있는데 백트래킹으로도 한번 풀어봐야겠다.