100년 뒤 개발자 한승규입니다.

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

그냥 부분집합 만들고, 그 부분집합이 S인지 확인하면 끝난다.

물론 방법은 쉽지만, 경우가 많이 나오기 때문에 신경쓰지 않으면 시간초과가 날 거 같기도 하다.

딱히 생각나는 방법은 없어서 재귀함수로 풀었다.

def find(param_list, cur_num):
    if len(param_list) == 0:
        if cur_num == S:
            return 1
        else:
            return 0

    return find(param_list[1:], cur_num + param_list[0]) + find(param_list[1:], cur_num)

각 수마다 넣을 지 말지에 대해서 2가지 경우의 수로 나누고, 선택할 수 있는 수가 없을 때의 합을 구해서 S가 맞는 지 확인한다.

지금 작성하면서 보니까 cur_num을 안쓰고 그냥 sum(list)로 했으면 더 깔끔했을 거 같다.

이렇게 하면 길이가 5개 일 때, 32가지의 경우가 나오게 된다.

하지만 이렇게 구하면 답은 맞지 않을거다.

공집합의 경우의 수도 포함하여 0을 반환하기 때문에 해당 경우는 빼주어야 한다.

import sys

N, S = map(int, sys.stdin.readline().split())

input_list = list(map(int, sys.stdin.readline().split()))


def find(param_list, cur_num):
    if len(param_list) == 0:
        if cur_num == S:
            return 1
        else:
            return 0

    return find(param_list[1:], cur_num + param_list[0]) + find(param_list[1:], cur_num)


result = find(input_list, 0)

if S == 0:
    print(result - 1)
else:
    print(result)

공집합은 0이기 때문에 S가 0일 때만 빼주도록 하자.