중복순열 구하기

문제설명

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

 

이 문제는 M번이 상수로 주어질 경우 다중 for문을 이용하여 쉽게 구할 수 있다. 하지만 지금처럼 몇번 뽑아야하는지 모를 때는 일일이 다중 for문의 변수를 i,j,k, ... 이런식으로 늘려줄 수가 없기에 재귀함수를 이용하여 M번의 레벨에서 멈추게 해주면 쉽게 구현할 수 있다.

function solution(n, m) {
  let answer = 0;
  function DFS(L) {
    if (L === m) {
      answer++;
    } else {
      for (let i = 1; i <= n; i++) {
        DFS(L + 1);
      }
    }
  }
  DFS(0);
  return answer;
}