백준 알고리즘 1182번 부분수열의 합(python)

브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다.

def dfs(depth, k):
    if depth == k and sum(li) == S:
        s.append(li)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1, k)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, S = map(int, input().split())
nums = list(map(int, input().split()))
li, s = [], []
for i in range(1, N+1):
    check = [0]*N
    dfs(0, i)
print(len(s))