백준 15652 N과 M(4)

문제

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

15652번: N과 M (4)

접근

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

➡️ 어렵게 생각할 것 없이 중복을 허용하는 순서가 상관없는 경우의 수를 구하라는 것이다: 중복순열. 순열 문제였던 백준 15650 N과 N(2) 문제에서 중복체크하는 checked 배열만 없애주면 된다.

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";

function dfs(level, start) {
  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  for (let i = start; i < N; i++) {
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
  }
}

dfs(0, 0);

console.log(result);