[Algorithm] 최대점수 구하기 (DFS) (⭐부분집합과 조합의 차이)

방법1) 부분집합

def DFS(L, time, sum):
    global res

    if time > m:
        return
    if L == n:
        if sum > res:
            res = sum
            print(L, time, sum)
    else:
        DFS(L+1, time+graph[L][1], sum+graph[L][0])
        DFS(L+1, time, sum)


if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = []
    for _ in range(n):
        a, b = map(int, input().split())
        graph.append([a, b])
    res = 0  # 최대 점수
    DFS(0, 0, 0)
    print(res)

방법2) 조합

def DFS(s, time, sum):
    global max
    if time > m:
        return
    if sum > max:
        max = sum
    for i in range(s, n):
        print(s, i, time, sum)
        DFS(i+1, time+graph[i][1], sum+graph[i][0])



if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = []
    for _ in range(n):
        a, b = map(int, input().split())
        graph.append([a, b])
    max = -2147000000
    DFS(0, 0, 0)
    print(max)