[백준 15655/javascript] N과 M (6)

백트래킹 문제

중복 불가이므로 중복을 확인할 배열을 만들어주고,

오름차순으로 결과가 나와야 하므로 미리 선택지 배열을 sort 후, 백트래킹 함수에 넣었다

앞의 수보다 뒤에 수가 더 커야 하므로 인자를 하나 더 전달하여 해결하였다

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

15655번: N과 M (6)

let input = [];

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (inp) => {
  let input = inp.shift().split(" ");
  let m = Number(input[1]);
  let arr = inp[0].split(" ").map((el) => Number(el));

  arr.sort((a, b) => a - b);
  let arrlen = arr.length;
  let arrisused = Array(arrlen).fill(0);
  let ans = [];
  let answer = [];

  const bt = (k, t) => {
    if (ans.length === m) {
      answer.push(ans.join(" "));
      return;
    }
    for (let i = t; i < arrlen; i++) {
      if (arrisused[i] === 0) {
        arrisused[i] = 1;
        ans.push(arr[i]);
        bt(k + 1, i + 1);
        arrisused[i] = 0;
        ans.pop();
      }
    }
  };
  bt(0, 0);
  console.log(answer.join("\n"));
};