[실버 3] 15649번 N과 M (1) ⭐️

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

const input = require("fs").readFileSync("ex.txt").toString();

const [N, M] = input.split(" ").map(Number);

const arr = Array.from({ length: N }, (_, i) => i + 1);
const visited = Array.from({ length: N }, () => false);
const selected = [];
let answer = "";

function dfs(arr, depth) {
  if (depth === M) {
    let result = [];
    for (let s of selected) result.push(s);
    answer += result.join(" ") + "\n";
    return;
  }

  for (let i = 0; i < N; i++) {
    if (visited[i]) continue;
    visited[i] = true;
    selected.push(arr[i]);
    dfs(arr, depth + 1);
    visited[i] = false;
    selected.pop();
  }
}

dfs(arr, 0);

console.log(answer);