[백준] - 15649 N과 M (1) (node.js)

문제링크

풀이

백트래킹을 사용했다. 재귀를 사용해서 현재 depth와 m이 같다면 (m개의 수를 고른 것이니까) 출력해주고 return한다. 그리고 이전에(재귀로 들어가기 전에) 1로 바꾸었던 visited를 0으로 바꾸고 기존에 넣어둔 수를 pop하는 식으로 구현했다. (return 되었다는 건 해당 숫자의 조합을 다 해봤다는 거니까)

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input[0].split(" ").map(Number);
let result = [];
let visited = new Array(n + 1).fill(0);

const backtracking = (depth) => {
  if (depth === m) { // m개의 수를 고른 것이니까
    console.log(result.join(" "));
    return;
  }

  for (let i = 1; i <= n; i++) {
    if (!visited[i]) {
      result.push(i);
      visited[i] = 1;
      backtracking(depth + 1); // 재귀
      visited[i] = 0;
      result.pop();
    }
  }
};

backtracking(0);