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

부분집합을 하는 문제라고 판단하여, 부분집합구하기 문제처럼 ch(체크) 리스트 만들어서 풀었는데 답이 안나오네요.. 무엇이 문제일까요? 강의를 보니 체크 리스트 사용하지 않으셨던데... 사용해야하는 것 아닌가요?

 

추가적인 질문으로, 부분집합과 조합 방식의 차이가 무엇인지 아직까지 잘 이해가 되지 않는데.. 부분집합은 가지치기가 본인 포함 전부 다 되고, 조합은 가지치기가 본인을 제외한 하위 부분만 되는게 맞나요?

부분집합을 조합처럼 구할 수 있고, 조합을 부분집합처럼 구할 수 있나요?

 

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

    if time > m:
        return 
    if L == n:
        if sum > res:
            res = sum
    else:
        for i in range(n):
            if visited[i] == 0:
                visited[i] = 1
                DFS(i, time+graph[i][1], sum+graph[i][0])
                visited[i] = 0
                DFS(i, 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])
    visited = [0]*n
    res = 0  # 최대 점수
    DFS(0, 0, 0)
    print(res)