인프런 커뮤니티 질문&답변

코드를 아래와 같이 짰고 테스트결과 123은 클리어, 4번은 시간초과가 나지만 답은 맞고 5번케이스는 무한루프에 빠지는것처럼 보이는데 이유를 도저히 모르겠습니다.

컷팅하기전 코드인데 시간이 엄청 많이 걸려서 그러는건가요 아님 코드에 문제가 있는건가요??

def dfs(idx, sum_w):
    global largest_w
    if sum_w > c:
        return
    elif sum_w > largest_w:
        largest_w = sum_w

    if idx == n:
        return

    dfs(idx+1, sum_w+puppies[idx])
    dfs(idx+1, sum_w)


c, n = map(int, input().split())
puppies = []
for _ in range(n):
    puppies.append(int(input()))

largest_w = 0
dfs(0, 0)
print(largest_w)