백준 알고리즘 18429번 근손실(python)

브루트포스 알고리즘 & 백트래킹 문제이다. 현재 근육량 + 현재 운동 키트 중량 - K가 0 이상일 때만 재귀 함수로

진입하고 depth(운동 일수)가 성공적으로 N이 되었다면 cnt를 올려주면 된다.

def dfs(depth, t):
    global cnt
    if depth == N:
        cnt += 1
        return ;
    for i in range(N):
        if check[i] or t+nums[i]-K < 0:
            continue
        check[i] = 1
        dfs(depth+1, t+nums[i]-K)
        check[i] = 0
        
N, K = map(int, input().split())
nums = list(map(int, input().split()))
check, cnt = [0]*N, 0
dfs(0, 0)
print(cnt)