[백준] 15649번 N과 M(1) / 파이썬(python)

# 문제 링크

www.acmicpc.net/problem/15649

15649번: N과 M (1)

# 관련 알고리즘 이론

jiwon-coding.tistory.com/34

백트래킹 (Backtracking)

# Soultion

DFS의 일종인 백트래킹에 대하여 공부를 한 뒤, 문제를 풀었다. (재귀함수)

n,m = list(map(int,input().split()))
 
s = []
 
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()
 

3. 재귀함수를 이용하여 m개의 수열을 저장하기 위한 리스트

6. 리스트에 들어간 수열들이 m개가 되면 리스트에 들어있는 숫자들을 모두 출력하고 함수를 나온다.

10. for문을 이용하여 1부터 n까지의 숫자들을 모두 확인

11. 리스트 s 중복여부 확인

12. 중복이 아니면 숫자 i를 리스트 s에 넣기

13. 현재 s=[1]인 상태에서 다음숫자를 넣기위하여 가지치기하기(재귀함수)

  -> 만약 n=4, m=2라면 밑과 같은 형태로 진행될 것이다.

      s : [1] -> [1,2] -> [1] -> [1,3] -> [1] -> [1,4]

                  출력   pop(2)  출력   pop(3)  출력