[DFS][JS] 중복순열

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
맨 마지막 총 경우의 수를 출력합니다.
▣ 입력예제 3 2
출력 예제 9

## 풀이 입력 옞로 생각해보자 순열은 순서가 다르면 다른 조합으로 친다. 따라서 우리는 중복 상관없이 1,2,3을 돌며 2개의 조합을 완성하면 된다.

function solution(n, m) {
  const ch = Array.from({length:m}, () => 0)
  let level = 0;
  let answer = [];
  
  function dfs(level) {
		if(level === m) {
      answer.push(ch.slice())
    }
    else {
			for(let i = 1; i<=n; i++) {
        ch[level] = i
        dfs(level + 1)
      }
    }
  }
  dfs(0)
  return answer.length;
}

solution(3, 2) //9

하나의 뎁스를 들어갈 때마다 뻗어나가는 가짓수는 1,2,3 3가지이기 때문에 for문을 돌며 재귀호출을 해준다. 이 때 거쳐간 숫자를 기억해 조합으로 나타내야 하기 때문에 ch배열에 넣어준다.

뎁스 레벨이 2개에 다다르면 저장해두었던 숫자 2개를 꺼내어 주면 된다.

Reference

• 자바스크립트 알고리즘 문제풀이 - 인프런