Inflearn Community Q&A

선생님 이 문제 부분집합으로 푸셨는데, 조합으로 구하면 안되나요? 부분집합과 조합의 차이가 무엇인가요?

아래처럼 조합으로 코드 짰는데 선생님께서 푸신 답변과 비슷한듯 다르네요.

for i in range(s, n+1)을 없이 푸셨는데... 조합에서는 필요하지 않나요?

 

def DFS(s, money):
    global max

    if s > (n+1):
        return
    if s == (n+1):
        if money > max:
            max = money

    for i in range(s, n+1):
        if i+graph[i][0] <= (n+1):
            DFS(i+graph[i][0], money+graph[i][1])
        DFS(i+1, money)

n = int(input())
graph = []
for _ in range(n):
    a, b = map(int, input().split())
    graph.append([a, b])

graph.insert(0, [0, 0])
max = -2147000000
DFS(1, 0)
print(max)