백준(baekjoon) 15650번: N과 M (2)(실버 3, 파이썬 PYTHON) - 백트래킹

문제

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

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

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

15650번: N과 M (2)

 

import sys

N,M=map(int,sys.stdin.readline().split())
list=[]

def dfs(num):
  global N,M,list
  if(num==M):
    print(*list)
    return
  for x in range(1,N+1):
    if(len(list)==0 or x>list[len(list)-1]): 
      list.append(x)
      dfs(num+1)
      list.remove(x)
      
dfs(0)

 

※ 백트래킹

 

 

● 중복되는 수열 (예를들어 [1,2] 와 [2,1]) 을 출력하면 안되므로 list에 아무 요소도 없거나 현재 수가 list의 가장 끝에 있는 요소보다 클 경우에 list에 append 해준다는 조건을 추가해준다.

 

 

결과

 

 

♣ 참고: N과 M(1)

 https://doyourbestcode.tistory.com/47

백준(baekjoon) 15649번: N과 M (1) (실버 3, 파이썬 PYTHON) - 백트래킹