문제 15649 ( C++ )

백트래킹 문제

한번 선택한 정수는 다시 선택할 수 없으므로 visited 배열을 이용하여 promising 한지 promising 하지 않은지 판별할 수 있습니다. 재귀적으로 깊이 들어가다가 M 개의 수를 선택하면 결과를 출력합니다

 

코드

#include <iostream>
  
using namespace std;
 
const int MAX = 9;
 
int N, M;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};
 
void dfs(int cnt) {
 
  if (cnt == M ) {
    for (int i = 0; i < M; i++ )
      cout << arr[i] << " ";
 
    cout << "\n";
    return ;
  }
 
  for (int i = 1; i <= N ; i++ ) {
    if (!visited[i]) {
      visited[i] = true;
      arr[cnt] = i;
      dfs(cnt + 1 );
      visited[i] = false;
    }
  }
 
}
 
int main(void) {
 
  cin >> N >> M;
 
  dfs(0);
 
  return 0;
}