[코테강의/JS] 중복순열

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

 

왜 이 문제에서 for 문이 아닌 재귀를 선택해야할까?

다음과 같은 코드로 로직을 짤 수도 있을 것이다. 

for (let i = 1; i <= 3; i++) {
  for (let j = 1; j <= 3; j++) {
    console.log(i, j);
  }
}

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

하지만 deps가 2가 아닌 3이 된다면 이중 for문이 아니라 3중 for문을 사용해야할 것이다. 계속 변하는 deps에 대응하기 위해서는 for문으로 접근하는 것이 아닌 dfs 를 통한 재귀로 접근을 해야했다.

 

배운점

1차원 배열을 선언할때 Array.from 을 사용해서 선언해보세요.

let temp = Array.from(Array(m),()=>0)

Array.from을 사용해서 2차원 배열을 선언해보세요!

let arr = Array.from(Array(n), ()=>Array(m).fill(0))

문제풀이

n = 4;
m = 3;
let temp = Array.from(Array(m), () => 0);
console.log(temp);
const dfs = (L) => {
  if (L === m) {
    let answer = "";
    for (let i = 0; i < m; i++) {
      answer += `${temp[i]} `;
    }
    console.log(answer);
  } else {
    for (let i = 1; i <= n; i++) {
      temp[L] = i;
      dfs(L + 1);
    }
  }
};

dfs(0);