[Python/파이썬] - 백준(BOJ) 1182번 : 부분수열의 합

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

1182번: 부분수열의 합

 

단순 브루트포스 문제.

1번 원소를 더한 후 2~n번 원소를 더하는 함수를 호출하고

그 함수에서는 3~n번 원소를 더하는 함수를 호출한다.

이 과정을 1~n번 원소 모두 실행하면 답이 나온다

 

누적 합을 이용하여 중간에 프루닝 하는 방법을 이용하려 했으나

n이 충분히 작아 시간초과가 나지 않을 것 같아 모든 원소를 탐색하였다.

def Back(sum, index):
    global answer
    sum += arr[index]
    if sum == m:
        answer += 1
    if index == n-1:
        return
    for i in range(index+1, n):
        Back(sum, i)

n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
answer = 0
for i in range(n):
    Back(0, i)
print(answer)