[python/파이썬] 백준 15650 N과 M (2)

[문제 출처]

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

15650번: N과 M (2)

 

[비슷한 문제 풀이]

 

기본 풀이는 아래의 문제와 동일하므로, 자세한 설명이 필요하다면 참고 부탁드립니다.

 

https://sodehdt-ldkt.tistory.com/197

[python/파이썬] 백준 15649 N과 M (1)

 

[소스 코드]

dfs 알고리즘을 사용해서 모든 경우의 수열을 출력하였다.

 

15649번 문제와 유사하나, 15649번 문제는 순열이었다면, 이번 문제는 조합이라는 점이 다르다.

조합이기 때문에 

예를 들어 1 2 3과 1 3 2는 중복되기 때문에 증가하는 순으로 출력된 1 2 3만 출력되어야 한다.

 

따라서 2가 배열에 들어있는 상태라면, 1부터 다시 순회하면 중복된 순열이 만들어지게 된다.

ex) n = 4, m = 2

1 2

1 3

1 4

2 1 (x)

2 3 (o)

2 4 (o)

...

따라서 마지막으로 배열에 들어간 숫자보다 큰 수부터 순회해야 한다.

조건문으로 배열에 숫자가 있다면 -1번째 숫자(마지막으로 저장된 수)보다 i가 큰 경우에만 dfs를 진행하도록 했다.

#15650

n,m = map(int, input().split())
sq = []
def dfs():
  if len(sq)==m:
    print(' '.join(map(str,sq)))
    return
  
  for i in range(1, n+1):
    if i not in sq:
      if sq:
        if sq[-1] > i:
          continue
      sq.append(i)
      dfs()
      sq.pop()

dfs()