1. 코드

15651번

자연수 N과 M이 주어졌을 때,
아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

2. 풀이

N,M = list(map(int,input().split()))

def nm_backtrack(n, m):
    
    result = [0] # 탐색한 경우의 수를 저장하는 상태공간 정의
    def backtrack(): # 상태공간을 DFS 방식으로 탐색
        if len(result) == m+1: # Depth가 tree 끝에 도달하면 값을 출력
            print(' '.join(map(str,result[1:])))
            return # Depth가 tree 끝에 도달하면 재귀 종료

        for i in range(1,n+1): # 1부터 n까지 1씩 증가
            result.append(i) # result에 추가한다.
            '''
            tree 가지를 재귀 형태로한번 더 뻗는다.
            위의 if문에 의해 Depth가 tree 끝에 왔다면
            출력하고 return 된다.
            '''
            backtrack()
            '''
            return되어 나온 tree의 가지 끝을 자른다.
            for 문에 의해 다음 i가 가지 끝에 나온다.
            '''
            result.pop()
                
    backtrack()

nm_backtrack(N, M)