[인프런 섹션8] 중복순열 구하기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션8] 중복순열 구하기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-29

1. 1부터 N까지 숫자 중 M번을 뽑기

• 중복허용 : 뽑았던 숫자를 또 뽑음
• 다 뽑으면 cnt++

2. DFS 종료조건

• m이 기준
• DFS의 매개변수 v : 숫자뽑은 횟수

if (v > m) {
  cnt++;
  console.log(res);
  return;
}

3. 뽑았던 숫자를 또 뽑는 로직

• 지금까지는 뽑은 경우/안뽑은 경우 두 가지로만 파익
• 지금은 순서대로 하나씩 뽑아야 함 --> for 반복문?

for (let i=1; i<=n; i++) {
  res.push(i);
  DFS(v+1);
  res.pop();
}

4. 출력형식

console.log(res.join(' ');

✍️소스코드

2021-06-29

let n = 3, m = 2;
let cnt = 0;
let res = [];

function DFS(v) {
  if (v > m) {
    cnt++;
    console.log(res.join(' '));
    return;
  }

  for (let i = 1; i <= n; i++) {
    res.push(i);
    DFS(v + 1);
    res.pop();
  }
}

DFS(1);
console.log(cnt);