https://www.acmicpc.net/problem/15649
: 1부터 까지 자연수 중에서 중복없이 M개를 골랐을 때의 경우의 수
중복없이 M개를 뽑는 모든 경우의 수를 구해야 함 == 백트래킹
N,M = map(int,input().split())
def dfs(arr):
if len(arr) == M :
print(' '.join(map(str,arr)))
return
for i in range(1,N+1):
if i not in arr :
arr.append(i)
dfs(arr)
arr.pop()
dfs([])
dfs 함수 인자로 배열을 사용 arr = []
arr 에 i 가 없다면 추가 후 , dfs 다시 돌려돌려 , 길이가 M 이 됐을 때 arr.pop()
백준 예제 입력 2 (N=4, M=2 ) 입력하여 이해해보장
코드 마지막줄 dfs([ ]) 실행 시 , i=1 일 때 dfs([1]) 이 실행됨.
dfs([1]) 실행 시, i=2 일 때 dfs([1,2]) 실행됨.
dfs([1,2]) 실행 시, if len(arr)==M 을 만족하므로, print 1 2. return 을 하게 됨.
그렇담 dfs([1]) 의 arr.pop() 으로 돌아감
전체그림 !!
N과 M 시리즈를 풀면서 백트래킹을 전보다는 더 잘 이해하게 되었다