부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을때 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한값이 S가 되는 경우의 수를 구하는 문제입니다.

제약조건
부분수열의 크기는 양수입니다.

풀이

모든 부분집합을 구하고 해당 부분집합의 합이 S인지 판단했습니다. 공집합을 고려해야합니다.

코드

'''
Created by jun on 21/05/21
'''
# idx를 뽑거나 뽑지 않는 경우의수.
# idx 현재 판단의 기준이되는 idx / 누적합 acc
def partial_sequence(idx: int, acc: int):
    if idx == len(sequence):
        return 1 if acc == S else 0
    return partial_sequence(idx + 1, acc + sequence[idx]) + partial_sequence(idx + 1, acc)


N, S = map(int, input().split())
sequence = list(map(int, input().split()))
res = partial_sequence(0, 0)
print(res - 1 if S == 0 else res)

새로 알게된 사실

공집합을 고려해야 합니다. 공집합은 하나도 안뽑는 경우의 수라고 할수있는데 이때의 합은 0이 됩니다.
부분집합의 크기가 양수인 경우 합이 0이 되는것과 공집합이기때문에 합이 0이되는것은 구분할수없습니다. 따라서 S가 0일때 공집합 개수에 대해서 제거해야 합니다.