[Algorithm] 🚩조합 구하기 (⭐중요!) (DFS)

⭐ 조합 구하기에서 응용되어 문제가 많이 출제되므로 중요한 부분 !!

def DFS(L, s):
    global cnt
    if L == m:
        for x in result:
            print(x, end=' ')
        print()
        cnt += 1
        return
    else:
        for i in range(s, n+1):
            result[L] = i
            DFS(L+1, s+i)  # 이 부분 틀림!


n, m = map(int, input().split())
result = [0]*m
cnt = 0
DFS(0, 1)
print(cnt)

처음에 위처럼 풀었는데 몇 군데에서 wrong 이 떴다.

DFS(L+1, s+i)가 잘못되었는데, 가지에 +1을 해야했다.

def DFS(L, s):
    global cnt
    if L == m:
        for j in range(m):
            print(res[j], end=' ')
        cnt += 1
        print()
    else:
        for i in range(s, n+1):
            res[L] = i
            DFS(L+1, i+1)  # 가지에 +1을 해야하므로 i+1


n, m = map(int, input().split())
res = [0]*(n+1)
cnt = 0
DFS(0, 1)
print(cnt)

이렇게!!

만약 s가 2이면 가지는 2, 3, 4 만 올 수 있다. 1은 오지 못한다.
조합 이기 때문에 (1,3) 과 (3,1) 중에 하나만 가능하다.