[백준] 1182 부분 수열의 합, python

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

1182번: 부분수열의 합

비트마스크를 사용한 조합문제이다.

dp를 사용하지 않았고 비트마스크를 사용해서 모든 부분 수열의 합을 구했다.

def main():
    N, S = map(int, input().split())
    seq = list(map(int, input().split()))

    answer = 0
    for select in range(1, 1 << N):
        tmp = 0
        for i in range(N):
            if select & (1 << i):
                tmp += seq[i]
        if tmp == S:
            answer += 1

    print(answer)

if __name__ == '__main__':
    main()