伯準-部分数列の和(1182)

Brute Force

質問する

入力

しゅつりょく

import sys
from itertools import combinations

n, target = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))
count = 0

for i in range(1, len(li) + 1):
    answer = list(combinations(li, i))
    for idx in range(len(answer)):
        if sum(answer[idx]) == target:
            count += 1
            
print(count)

import sys
input = sys.stdin.readline

n, target = map(int, input().split())
li = list(map(int, input().split()))

answer = 0
def subSet(idx, total):
    global answer

    if idx >= n:
        return
    total += li[idx]
    if total == target:
       answer += 1
    subSet(idx + 1, total - li[idx]) # 방금 누적했던 원소값을 다시 빼서 다음 인덱스의 원소값을 더하지 않는 상태
    subSet(idx + 1, total) # 다음 인덱스 원소값을 더한 상태에서 그대로 다시 재귀호출.

subSet(0, 0)
print(answer)