[알고리즘] JavaScript 순열과 조합 알고리즘 구현하기 (순열 편)

function permutations(n, arr) {
  const answer = [];

  // n개의 인덱스를 가진 배열을 확보한다.
  // [empty, empty];
  const temp = Array(n);

  // 인덱스가 사용중인지 check하기 위한 배열을 선언한다. 
  // 0은 사용안함 / 1은 사용중
  const ch = Array.from({ length: n }, () => 0);

  // L: 현재 뎁스 레벨
  function DFS(L) {
    if (L === n) {

      // 매개변수 L이 n과 같아지면 answer에 push해준다.
      // slice() 메서드를 사용한 이유는 재귀를 돌며 temp가 바뀌기 떄문이다.
      answer.push(temp.slice());
    } else {
      for (let i = 0; i < arr.length; i++) {

        // ch[i]가 0이라면
        if (ch[i] === 0) {
          
          // ch[i]를 1로 바꾸어 현재 사용하고 있다고 설정한다.
          ch[i] = 1;

          // temp[L] 현재 레벨에 맞는 숫자를 넣어준다.
          temp[L] = arr[i];

          // 레벨을 1 올려준 뒤 DFS 재귀함수를 호출한다.
          // 레벨이 n과 같아지면 answer에 push후 종료할 것이고
          // 아닐 경우 현재 ch에 체크된 사용중 인덱스를 제외하고
          // for()문이 돌며 레벨이 맞춰질 때 까지 재귀함수를 실행할 것이다.
          DFS(L + 1);

          // 사용을 완료했으면 ch[1]에 다시 0을 넣어 사용하지 않음으로 설정한다.
          ch[i] = 0;
        }
      }
    }
  }

  // 레벨 0부터 실행한다.
  DFS(0);

  return answer;
}

console.log(permutations(2, [1, 2, 3]));
// [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]