[실버3] 15649번 : N과 M(1)

🛠 문제

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

👩🏻‍💻 해결 방법

조합으로 풀 수 있는 문제이지만 백트래킹으로 풀기 위해 노력했다
dfs를 사용해 M개의 값이 out 리스트에 저장됐을 경우 출력해주었다
visit[i]=True를 해주었다가 재귀 후 다시 False로 해주는 것이 중요했다

소스 코드

n, m = map(int, input().split())
visit = [False] * (n + 1)
out = []

def solve(count, n, m):
  if count == m:
    print(' '.join(map(str, out)))
    return 
  
  for i in range(1, n+1):
    if visit[i] == False:
      visit[i] = True
      out.append(i)
      solve(count+1, n, m)
      visit[i] = False
      out.pop()

solve(0, n, m)