백준 15652 N과 M (4)

문제

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

제한 사항

• 1부터 N까지 자연수 중에서 M개를 고른 수열
  같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입출력 예

풀이

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 = [];
  function dfs(start, cnt) {
    if (cnt === m) {
      answer.push(tmp.join(" "));
    } else {
      for (let i = start; i <= n; i++) {
        tmp.push(i);
        dfs(i, tmp.length);
        tmp.pop();
      }
    }
  }
  dfs(1, 0);
  return answer.join("\n");
};

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

• 중복 조합
• 각 숫자를 중복을 뽑아도 되지만, 조합된 숫자가 중복되면 안된다.