8-8. 중복 순열 구하기 (DFS)// 조합,순열 문제에서 for문 아닌 재귀 함수 쓰는 이유

문제

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

풀이

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

console.log(solution(3, 2));

 

 

많은 순열 , 조합 문제에서 for문을 사용하지 않고 재귀 함수를 사용하는 이유

재귀함수를 통한 4번의 중복 순열 구하기

 

for문을 통해 4번의 중복 순열을 구할 때

function solution(n, m) {
  let answer = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < m; j++) {
      for (let k = 0; k < m; k++) {
        for (let s = 0; s < m; s++) {
          console.log(i, j, k, s);
        }
      }
    }
  }
  return answer;
}

console.log(solution(4, 4));

 

둘의 차이점은 몇 번 뽑는지 일정하지 않을 때 for문에서는 for문을 추가하여서 코드 짜기가 어렵거나 불가능할 것 같은데 재귀 함수에서는 L === m으로 몇 번 트리를 생성할지 따로 안 정해도 되어서 재귀 함수를 사용하기에 용이합니다.