문제

문제 바로가기

N과M
위 문제에서 중복허용이라는 조건이 추가 되었다.
따라서 시간복잡도는 O(n!)에서 O(n^n)으로 변경된다.

풀이

import sys
input=sys.stdin.readline
c=list()
n,m=map(int,input().split())
def dfs(depth): 
    global n,m    
    for x in range(1,n+1):        
        c.append(x)
        if depth==m:
            print(' '.join(map(str,c)))                
        else:                
            dfs(depth+1)
        c.pop()            
dfs(1)

풀이는 N과M과 거의 비슷하고
조건을 삭제하기 때문에 로직은 오히려 더 간단하다.
겹치는 수가 있으므로 remove 대신 pop을 해줘야 순서가 꼬이지 않는다.