[SWEA] 2817. 부분 수열의 합

2817. 부분 수열의 합

문제 풀이

• 지난 '햄버거 다이어트' 와 같이 'PowerSet 알고리즘'을 사용

t = int(input())

for i in range(1, t+1):

    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    ans = 0

    def powerset(idx, total):
        global ans
        if total == k:  # total이 k와 같으면 횟수 ans += 1
            ans += 1
            return

        if idx >= n:   # n을 넘으면 return
            return

        powerset(idx + 1, total + arr[idx])
        powerset(idx + 1, total)

    powerset(0, 0)
    print(f"#{i} {ans}")