[백준 15652] N과 M(4) with 파이썬

요구사항

중복을 허용하여 n개 중 m개를 뽑는다

 

참고

n개 중 m개를 뽑느데 현재 index보다 전에 있는 원소는 뽑을 수 없다

1. dfs를 이용하여 문제를 푼다

-> 중복을 허용함으로 dfs 진입 시 현재(now)부터 끝까지 탐색할 수 있도록 한다

-> 현재(now)부터 끝은 for 안에는 진행되는 루틴이다

 

풀이

n,m=map(int,input().split())
visit=[0]*100
my_vec =[]
def Com(now, cnt):
    if(cnt==m):
        for i in my_vec:
            print(i,end=' ')
        print()
        return

    for i in range(now,n+1):
        #방문 여부 체크안하고 그냥 바로 현재 원소부터 dfs로 탐색할 수 있도록 한다
        #if(visit[i]==0):
        #    visit[i]=1
        my_vec.append(i)
        Com(i,cnt+1)
        my_vec.pop()
        #    visit[i]=0

Com(1,0)