문제

문제 바로가기

N과M
위 문제에서 중복허용과 비내림차순이라는 조건이 추가되었다.

풀이

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

풀이는 N과M과 거의 비슷하고
조건을 삭제하기 때문에 로직은 오히려 더 간단하다.
겹치는 수가 있으므로 remove 대신 pop을 해줘야 순서가 꼬이지 않는다.
또한 비내림차순으로 출력해야하므로 자식 노드가 부모노드보다 크지 않게 현재 노드+1을 출발점으로 보내준다.