1. 문제

15652번

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

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

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씩 증가
            if i >= max(result): # i가 상태공간에 없을 때,
                result.append(i) # result에 추가한다.
                '''
                tree 가지를 재귀 형태로한번 더 뻗는다.
                위의 if문에 의해 Depth가 tree 끝에 왔다면
                출력하고 return 된다.
                '''
                backtrack()
                '''
                return되어 나온 tree의 가지 끝을 자른다.
                for 문에 의해 다음 i가 가지 끝에 나온다.
                '''
                result.pop()
                
    backtrack()

nm_backtrack(N, M)