순열 알고리즘

문제 : 1부터 4 까지의 숫자중 2개를 고르시오

• 순열은 중복을 허용한다
  1,1 1,2 1,3 1,4 2,1 .....
• for문이 2번 돌아간다고 생각하면 직관적으로 이해하기 쉽다.
  하지만 5개 중에 3개를 골라야 한다면? 만약 4개를 골라야 한다면?? for문을 계속 변경해줘야 한다
  == > 코드를 재사용하기 위해서는 재귀함수의 사용이 필요하다

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

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

1. tem은 뽑은 숫자를 임시 보관하고 정답에 넣어주는 배열이다
2. L은 level을 의미하며 0에서 출발해서 뽑아야 하는 숫자수에 도달하면 재귀함수를 종료시켜준다

• 0에서 출발하는 이유는 index가 0부터 시작하기 때문이다

3. 스택은 LIFO 이기 때문에 for문에서 tem[0]=1,2,3,4는 뒤 재귀함수가 끝날 때 까지 고정! 이 된다
   DFS(1)일 때 다시 for문을 만나고 다시 재귀함수를 만나는데 L===n이 되면 트리가 더 뻗어나가지 못한다 그래서 tem[1]=1,2,3,4를 해주고 DFS(0)의 for문으로 돌아간다

• tem[0]=1 일때 tem[1]=1 tem[1]=2 tem[1]=3 tem[1]=4 까지 한뒤 다시 DFS(0)의 for문이 진행되어서 tem[0]=2 tem[1]=1 tem[1]=2 tem[1]=3 tem[1]=4

4. tem.slice()해서 정답 배열에 넣어주는 이유는 tem을 바로 push를 하게되면 주소가 들어가서 마지막 tem으로 다 통일이 되어버린다 그래서 복사를 해줘서 넣어준다