💡문제 분석 요약

• 주어진 N개의 숫자 중에서 중복을 허용하지 않고 M개의 숫자를 뽑는 모든 가능한 조합을 구한다.
• 중복된 숫자가 있을 경우 결과에서 중복된 조합은 제거해야 한다.
  • 입력
    • 첫째 줄에 N과 M이 주어지며 (1 ≤ M ≤ N ≤ 8).
    • 둘째 줄에 N개의 숫자가 주어진다 (1 ≤ 숫자 ≤ 10000).
  • 출력
    • 사전 순으로 정렬된 M개 숫자 조합을 출력해야 한다.

💡알고리즘 설계

• 입력 처리: N과 M을 입력받고, N개의 숫자를 배열에 저장한다.
• 정렬: 입력된 숫자를 정렬하여 사전 순으로 출력할 수 있도록 한다.
• 재귀 함수 사용: M개를 선택하기 위해 재귀적으로 함수를 호출한다.
  • 기저 조건: M개를 모두 선택한 경우, 선택한 조합을 출력한다.
  • 순회 및 선택: 정렬된 배열을 순회하며, 중복된 숫자는 건너뛴다.
• 중복 처리: 같은 숫자에서 발생할 수 있는 중복 조합을 방지하기 위해 이전에 선택된 숫자와 비교한다.
• 출력: 중복을 제거한 조합을 출력한다.

💡코드

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

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

const [N, M] = input[0].split(' ').map(Number);
const numbers = Array.from(new Set(input[1].split(' ').map(Number))).sort((a, b) => a - b);

const result = [];
const visited = new Array(numbers.length).fill(false);

function backtrack(combination) {
  if (combination.length === M) {
    result.push(combination.join(' '));
    return;
  }

  for (let i = 0; i < numbers.length; i++) {
    if (visited[i]) continue; // 이미 사용한 숫자는 건너뛴다.

    // 중복 방지: 현재 숫자가 이전 숫자와 같고, 이전 숫자가 사용된 경우는 건너뛴다.
    if (i > 0 && numbers[i] === numbers[i - 1] && !visited[i - 1]) continue;

    visited[i] = true; // 사용한 숫자 표시
    backtrack([...combination, numbers[i]]);
    visited[i] = false; // 사용한 숫자 복구
  }
}

backtrack([]);

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

💡시간복잡도

• 정렬: O(N log N) (N개의 숫자를 정렬하는 데 필요한 시간)
• 조합 생성: O(N^M) (최악의 경우 모든 조합을 생성할 수 있고, M이 작으므로 N이 크더라도 수행 가능하다.)