백준 15650번. N과 M (2) (Python / 파이썬)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
 - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
 - 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

문제 풀이

자연수 N과 M이 주어졌을 때, 1부터 N까지의 자연수 중

중복 없이 M개를 고른 수열을 구하는데 이때 고른 수열은 오름차순이어야 합니다.

 

15649번 문제와 마찬가지로 Back Tracking을 이용하여 문제를 해결했습니다.

이때, 15649번과 다른 점은 고른 수열이 오름차순이어야 한다는 것입니다.

 

따라서 dfs 함수에 start 매개변수를 추가해주었습니다.

고른 수열은 오름차순이어야 하므로 항상 나보다 작은 원소는 고려하지 않습니다.

즉, 나보다 큰 원소만 고려하면 되므로 

반복문을 현재 해당 자연수부터 시작되도록 해줍니다.

그런다음 재귀함수를 수행할 때 i + 1 즉, 해당 자연수의 다음 자연수를 넘겨주어

재귀함수를 수행시켜줍니다.

이렇게 하면 고른 수열이 항상 오름차순이 될 수 있습니다.

---

My Code 

n, m = map(int,input().split()) # 자연수 N과 M

array = [] # 길이가 M인 수열을 저장할 list

def dfs(start):
    if len(array) == m: # 길이가 M이 됐다면
        for i in array: # array 원소들 출력
            print(i, end = ' ')
        print()
        return # 호출 됐던 위치로 돌아가기
    
    for i in range(start, n + 1): # 현재수보다 큰 수만 수행
        if i not in array: # i가 array 안에 없다면
            array.append(i) # i를 array에 삽입
            dfs(i + 1)      # i 다음 수로 재귀함수 수행
            array.pop()     # array의 오른쪽 원소 삭제

dfs(1)