[DFS][조합] - 수들의 조합

문제

n개의 수들을 k개 만큼 뽑아 더한 수들의 합이 m의 배수인 경우를 다 구하라

문제풀이

def DFS(L,s,total):

    global cnt 
    if L == k:
        if total%m == 0:
            cnt += 1
    else:
        for i in range(s, n):
            DFS(L+1, i+1, total + a[i] )
    


if __name__ =="__main__":
    n, k = map(int,input().split())
    a = list(map(int,input().split()))
    m = int(input())
    cnt = 0
    DFS(0,0,0)

• k개 만큼씩 수들의 조합을 뽑아낸 뒤 해당 k의 조합의 합이 m의 배수라면 cnt를 1개 증가시켜준다.
• L = 노드 레벨
• s는 그 앞전에 확인했던 부분을 빼주기 위함이다.
• total에 해당 값을 더해가며 이 부분이 m으로 나눴을 때 나머지가 0이라면 배수이기 때문에 cnt를 증가한다.