[Python] 백준 온라인 저지 N과 M 시리즈(2) - 15650번

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

 

 

 

[Python]

 

풀이 방법:

 

15649번과의 차이점은 이 문제에서는 [1,2], [2,1]과 같은 경우는 중복되는 경우로 보고 [1,2]만 출력해야한다.

 

 

코드:

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [0 for _ in range(n)]
lists = []


def dfs(cnt): 
    if cnt == m: 
        print(' '.join(map(str, lists)))
        return
    
    for i in range(n): 
        if visited[i] == 0: 
            visited[i] = 1 # 중복 제거 
            lists.append(i+1) 
            
            dfs(cnt+1) # 다음 깊이 탐색 
            lists.pop() # 탐사한 내용 제거
            
            # 순열 부분과의 차이점 
            for j in range(i+1, n): 
                visited[j] = 0 
                
dfs(0)