15650. N과 M (2)

https://www.acmicpc.net/problem/15650

 

조합 문제이다.

구현에 있어서 순열과 다른 점은,

조합의 경우 순서가 없기 때문에 check만 확인해서 True인 것들만 출력하면 되지만

순열의 경우 1, 2, 5와 1, 5, 2가 다른데 check 확인 후 출력하면 항상 앞에서부터 1, 2 5로 출력이 될 것이기 때문이다.

따라서 조합은 뽑은 수열을 위한 리스트가 따로 없음을 유의하면 순열과 다른 점은 없다.

순열과 달리 시작부가 dfs(0, 0) = dfs(idx, cnt) 으로 시작하는 것은

dfs를 재귀호출 했을 때 리스트의 처음부터 다시 탐색해야 하는 '순열'과는 달리

조합은 지금까지 탐색했던 것들은 다시 탐색할 필요가 없기 때문에 현재 인덱스를 저장해놓기 위함이다.

(설명추가: 조합은 1을 한번 선택해서 조합을 꾸렸다면, 그게 1이 포함된 조합의 전부이다.

즉, 1이 포함된 조합 선택이 끝나면, 그 이후로는 1을 선택하지 않을 것이다. )

n, m = map(int, input().split())
lst = []
check = [False] * n
for i in range(1, n+1):
    lst.append(i)

def Print():
    for i, v in enumerate(check):
        if v == True:
            print(lst[i], end = ' ')
    print("")

def dfs(idx, cnt):
    if cnt == m:
        Print()
        return
    for i in range(idx, n):
        if check[i] == True:
            continue
        check[i] = True
        dfs(i, cnt+1)
        check[i] = False

dfs(0, 0)  # lst의 0번째 인덱스부터 살펴보면서 / 0번째 수열부터 뽑을 것임

 

 

https://yabmoons.tistory.com/99

를 참고했다.