백준 15649 N과 M(1)

문제

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

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

제한 사항

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

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split(" ").map(e=>+e);
let [n,m] = [...input];

const solution = (n, m) => {
  let answer = [];
  let visited = new Array(n + 1).fill(0);
  let tmp = new Array(m).fill(0);
  function dfs(L) {
    if (L === m) {
      answer.push(tmp.join(" "));
    } else {
      for (let i = 1; i <= n; i++) {
        if (!visited[i]) {
          visited[i] = 1;
          tmp[L] = i;
          dfs(L + 1);
          visited[i] = 0;
        }
      }
    }
  }
  dfs(0);
  return answer.join("\n");
};
console.log(solution(n,m));

백트래킹.

같은 수 예를 들어 (1,1)은 안되게 하는 순열.