백준 15650 N과 M(2)

문제

자연수 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 tmp = new Array(m).fill(0);
  function dfs(L, s) { // 반복문에 사용할 s(start)변수
    if (L === m) {
      answer.push(tmp.join(" "));
    } else {
      for (let i = s; i <= n; i++) {
        tmp[L] = i;
        dfs(L + 1, i + 1);
      }
    }
  }
  dfs(0, 1);
  return answer.join("\n");
};

console.log(solution(n,m));

• 조합
• 첫번째에 1을 뽑았다면 2, 3, 4 를 뽑을 수 있고
  첫번째에 2를 뽑았다면 3, 4를 뽑을 수 있다.
• 조합에서 1,2 와 2,1은 같은 수열로 취급한다.

const solution = (n, m) => {
  let answer = [];
  let tmp = [];
  const visited = new Array(n + 1).fill(0);
  function dfs(s, cnt) {
    // 반복문에 사용할 s(start)변수
    if (cnt === m) {
      answer.push(tmp.join(" "));
    } else {
      for (let i = s; i <= n; i++) {
        if (!visited[i]) {
          visited[i] = 1;
          tmp.push(i);
          dfs(i, tmp.length);
          visited[i] = 0;
          tmp.pop();
        }
      }
    }
  }
  dfs(1, 0);
  return answer.join("\n");
};

console.log(solution(4, 2));

• 이 패턴이 더 사용하기 편한 것 같다.
• start와 cnt(L과 같은 용도)를 이용하고 cnt를 tmp.length로 바꾸며 사용한다.
• visited 배열만 없애면 바로 중복조합을 구하는 형태가 된다.