백준 15649번 N과 M (1) JavaScript 풀이 [백트래킹]

백준 15649번 N과 M (1) 문제를 자바스크립트로 백트래킹 알고리즘을 이용해서 풀어보았다. 

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

 

let fs = require('fs');
let [n, m] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

// 1부터 n까지 수가 차례대로 들어있는 배열
let numbers = new Array(n).fill(0).map((v, i) => i+1);
// 방문 처리 배열
let visited = new Array(n).fill(false);
// 순열이 들어갈 배열
let sequence = [];

function backtrack (depth) {
	// m개까지 순열이 완성되면 출력 및 함수 종료
  if (depth == m) {
    console.log(sequence.join(" "))
    return;
  }

  for (let i=0; i<n; i++) {
    // 방문처리 안된 것만 진행
    if (!visited[i]) {
	    // 방문 처리 및 순열 배열에 삽입
      visited[i] = true;
      sequence.push(numbers[i]);
      // 재귀
      backtrack(depth + 1);
      // 방문 해제 및 순열 배열에서 삭제
      visited[i] = false;
      sequence.pop();
    }
  }
}

backtrack(0);