백준 15649번. N과 M (1) (Python / 파이썬)

문제

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

입력

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

출력

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

---

문제 풀이

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을

모두 구하는 문제입니다.

 

Back Tracking 방법을 이용해 문제를 해결했습니다.

먼저, 수열을 삽입할 빈 list = array를 만들어주었습니다.

그 후 1부터 N까지 반복문을 수행하는데,

중복이 없어야 하므로 해당 숫자가 array안에 없다면

해당 숫자를 array에 삽입해줍니다.

 

그런 다음 재귀함수를 이용하여 다시 함수를 실행해줍니다.

만약 array의 길이가 m이라면 원하는 수열을 찾은 것이므로

array 안의 수들을 출력해줍니다. 그런 다음 호출된 위치로 돌아갑니다.

호출 된 위치로 돌아가면 pop() 함수를 만나게 됩니다. 따라서

array의 오른쪽 원소를 삭제한 뒤 나머지 반복문을 실행합니다.

 

이 과정을 반복하면 중복 없이 M개를 고른 수열들을

구할 수 있습니다.

---

My Code

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

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

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

dfs()