[BJ] 15649 - N과 M(1) (백트레킹 기초)

 

백트레킹은 모든 경우의 수를 재귀적으로 탐색할떄 사용한다.

for문으로도 가능하지만 n개의 숫자가 늘어날수록 중첩for문을 해야하니 효율적이지 못할 수 있다.

 

1. 아이디어
- 백트레킹 재귀함수 안에서, for문 돌면서 숫자 선택(이떄 방문여부 확인)
- 재귀 함수에서 m개를 선택할경우 출력
- n은 사용할 숫자 갯수 m은 열

2. 시간복잡도
백트레킹은 중복이 가능할시 O(N^N), N = 8까지
중복이 불가시 O(N!) N = 10까지
중복 불가 조건 8까지

3. 자료구조
방문 여부 확인 bool[]
선택값 입력 배열 int[]

 

N = 4 M = 3일떄 구조

 

예제입력2