boj15649 N과 M (실버3) - 백트래킹

문제 링크: https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

내 풀이

1) 수열을 담을 리스트 하나 생성 arr = list()

2) dfs() 함수 만든다.

- 탈출조건은 arr 리스트의 길이가 m이 된 경우 출력하고 리턴한다.

- 1부터 n까지 반복하며 arr에 들어있지 않은 수를 append()한다. 

- 그리고 dfs() 재귀함수 반복

- 재귀가 끝나면 backtracking 해서 그 다음으로 넘어간다. pop()

 

# boj15649 N과 M
# 실버3

# 메모리 30840 KB
# 시간 212 ms

n, m = map(int, input().split())
arr = list()

def dfs():
    # 탈출 조건 : 수열 길이가 m 됐을 때.
    if len(arr) == m:
        print(' '.join(map(str, arr)))
        return

    # arr에 오름차순으로 append
    for i in range(1, n+1):
        if i not in arr:
            arr.append(i)
            dfs()
            arr.pop() # backtracking
dfs()