💡문제 분석 요약

• 1부터 N까지의 자연수 중에서 M개를 고른 수열을 출력하는 문제다.
• 중복된 숫자를 선택할 수 있으며, 순서가 중요한 중복 순열을 구하는 문제다. 구한 수열을 사전 순으로 출력해야 한다.
  • N: 1부터 N까지의 자연수를 사용한다.
  • M: 선택할 수열의 길이.
  • 중복 허용: 같은 숫자를 여러 번 선택할 수 있다.
  • 순서가 다르면 다른 수열로 본다.

💡알고리즘 설계

1. 백트래킹을 사용하여 M개의 숫자를 선택하는 모든 경우를 탐색한다.
2. 각 단계에서 1부터 N까지의 수 중 하나를 선택하고, 이를 중복해서 선택할 수 있다.
3. M개의 수를 선택하면 결과를 저장하고 출력한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split(' ');

const N = parseInt(input[0]);
const M = parseInt(input[1]);

const result = [];
const sequence = [];

// 백트래킹 함수
function backtrack(depth) {
  // 수열이 M개 선택되었을 때 출력
  if (depth === M) {
    result.push(sequence.join(' '));
    return;
  }

  // 1부터 N까지 수 선택 가능 (중복 허용)
  for (let i = 1; i <= N; i++) {
    sequence.push(i); // 숫자 선택
    backtrack(depth + 1); // 다음 단계로 이동
    sequence.pop(); // 선택한 숫자 제거 (백트래킹)
  }
}

backtrack(0);

console.log(result.join('\\n'));

💡시간복잡도

• 중복을 허용한 순열을 구하는 문제다.
• 각 자리에 1부터 N까지의 숫자를 선택할 수 있으며, M개의 숫자를 고른다.
• 따라서 시간 복잡도는 O(N^M) 이다.
  • 재귀 깊이: M (수열의 길이)
  • 각 자리에서 선택 가능한 수의 개수: N (1부터 N까지)