부분수열의 합
https://www.acmicpc.net/problem/1182
예제 입력 1
5 0
-7 -3 -2 5 8
예제 출력 1
1
풀이
백트래킹을 공부하면서 바킹독님의 도움을 많이 받았다.
생각해보면 주어진 수열의 각 원소들은 선택사항이 2가지이다. 합해지는 수열에 포함되거나 안되거나
그래서 수열의 원소가 n개일 때 부분집합의 개수는 2^n이고 공집합을 제외하면 2^n-1이 된다.
백트래킹 함수에서 파라미터를 두 개 받는데 k는 몇 번째 원소인지(k가 n이 되면 종료), sum은 수열의 값을 더해가면서 입력으로 주어지는 s와 같은지 비교해야 한다.
이 함수에서 base case는 k가 n이 될 때이다. 이때의 합이 s와 같다면 카운트 1 더해준다.
그리고 수열의 값이 더해지거나 안더해지거나 경우가 2가지 있으므로 2가지 경우를 나눠서 적어주면 끝이다.
백트래킹 쭉 돌고 마지막에 s가 0이면 카운트에서 1을 빼줬는데 그 이유는 공집합인 경우 더해진 수열의 값이 아무것도 없는데 카운트로 s가 0이므로 더해줬기 때문이다.
코드
import sys
input = sys.stdin.readline
n, s = map(int, input().split())
l = list(map(int, input().split()))
global cnt
cnt = 0
def back(k, sum):
global cnt
if k == n:
if sum == s:
cnt += 1
return
back(k+1, sum+l[k]) # 포함되거나
back(k+1, sum) # 포함 안되거나
back(0, 0)
if s == 0: cnt -= 1
print(cnt)
