BOJ : 1182 부분수열의 합

순열이므로 index를 이용했다.

visit 은 부분수열 숫자들의 index의 리스트들로 이루어진 리스트.
해당 부분수열의 마지막 index보다 큰 index가 visit 에 추가된다.

import sys
from collections import deque

num, s = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().strip().split()))

count = 0
visit = deque([[i] for i in range(len(numbers))])

while visit:
    x = visit.popleft()
    sum_x = sum([numbers[i] for i in x])
    if sum_x == s:
        count += 1
    for i, num in enumerate(numbers):
        if x[-1] < i :
            new = x + [i]
            visit.append(new)

print(count)

좋은 웹페이지 즐겨찾기