백준 1182 부분수열의 합

과정

• 모든 부분 집합을 구하기
  -> combination 구현해서 모든 경우의 합 확인
• 하나씩 더하는 경우와 더하지 않는 경우 가짓 수를 보면서 합이 같게 되면 답에 1씩 더해줌
  -> 백트래킹
  • idx랑 subsum을 입력 받는 함수를 만듦
  • idx가 N이랑 같으면 함수 종료
  • subsum에 값을 더함
  • 더한 값이 S랑 같으면 cnt 에 1 추가
  • idx는 1 더해주고, 더한 경우에서 함수 재귀 실행, 더하지 않은 경우에 함수 재귀 실행

import sys
input = sys.stdin.readline
N, S = map(int, input().split())
lst = list(map(int, input().split()))
cnt = 0

def main(idx, subsum):
    global cnt
    if idx >= N:
        return
    subsum = subsum + lst[idx]
    if subsum == S:
        cnt += 1
    main(idx + 1, subsum)
    main(idx + 1, subsum - lst[idx])
main(0, 0)
print(cnt)