백준 15651 N과 M(3)

문제

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

15651번: N과 M (3)

접근

백준 15651 N과 M(1) 과 같이 순열 문제이다.

단, 중복을 허용하기에 check 배열의 기능을 삭제해 주었다.

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";
const checked = Array(N).fill(false);

function dfs(level, start) {

  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }
  
  for (let i = start; i < N; i++) {
    if (checked[i]) continue; // backtracking
    checked[i] = true;
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
    checked[i] = false;
  }
}

dfs(0, 0);

console.log(result);