백준 15650 N과 M(2)

문제

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

15650번: N과 M (2)

접근

문제 15649 N과 M(1) 과 비교했을 때,

• 고른 수열은 오름차순이어야 한다.

 

라는 조건이 추가됐다. 즉, [4,3] 의 경우 [3,4] 로 정렬되어 경우의 수 [4,3]와 [3,4]는 같은 것으로 간주된다.

 

N과 M (1)는 재귀를 위한 for loop에서 index를 항상 맨 처음부터 다시 돌았다면(모든 경우의 수를 위해), 이 문제에서는 지난 숫자는 제외하고 for loop을 진행한다(중복을 피하기 위해)

풀이

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;
    
    checked[i] = true;
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
    checked[i] = false;
  }
}

dfs(0, 0);

console.log(result);