알고리즘 스터디를 진행하면서 DFS관련 문제를 풀고 있습니다.
헷갈리는 순열과 조합 개념을 정리해봅니다! 🧹

📍 순열(permutation)

순열은 순서를 고려해 정렬을 만드는 경우의 수 라고 할 수 있습니다.
예를 들어 1, 2, 3 이 주어지면 123, 132, 213, 231, 312, 321가 순열이 됩니다. (123과 132를 다른 것으로 칩니다!)

💡 같은 수는 중복해서 뽑으면 안되기 때문에 해당 수에 대한 사용을 체크하는 배열을 체크배열을 따로 사용합니다.

👾 코드로 구현하기

//순열 구하기
function solution(n, m, arr){
  let temp = Array.from({ length: m }, ()=>0);  //m개의 인덱스를 가진 배열을 확보
  let checkArr = Array.from({ length: n }, ()=>0);
  let answer = [];
  
  // L: 현재 뎁스 레벨
  function DFS(L){
    if (L === m){
      answer.push(temp.slice()); // L이 m과 같아지면 복사 후 answer에 push(재귀를 돌며 temp가 바뀌기 때문에 slice() 함수 사용)
    }else{
      for (let i=0; i<n; i++){
        if (!checkArr[i]){
          checkArr[i] = 1  //해당 노드(i)에 방문했기 때문에 1로 체크
          
          temp[L] = arr[i]; // temp의 L 인덱스에 현재 레벨에 맞는 숫자를 넣어줌

          DFS(L+1); //다음 Level로 이동
          
          checkArr[i] = 0  //사용 완료 후 다시 부모 노드로 올라갈 때 체크 값을 0으로 복구
        }
      }
    }
  } 
 
  DFS(0)
  return answer;
}


const arr = [1, 2, 3];
solution(3, 3, arr);

📍 조합(combination)

조합은 순서에 고려하지 않고 정렬을 만드는 경우의 수 라고 할 수 있습니다. 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합이라고 하고 nCr이라고 표현합니다.

순열 시간 복잡도: O(n!)
조합 시간 복잡도: O(2ⁿ)

예를 들어 1, 2, 3, 4 가 주어지면 123, 124, 134, 234가 조합이 됩니다. (순열과 다르게 123과 132를 같은 것으로 칩니다!)

👾 코드로 구현하기

// 조합 구하기

function solution(n, m){
  let answer = [];
  let tmp = Array.from({ length: m }, () => 0); //바뀌는 조합 계속 저장하는 배열

  const DFS = (L, s) => {
    if (L === m) {
      answer.push(tmp.slice());
    } else {
      for (let i = s; i <= n; i++) {
        tmp[L] = i; //1,2,3,4로 돌고있는 for문의 i를 L(레벨) 인덱스에 맞춰 넣어줌
        DFS(L + 1, i + 1); //L 1증가, i에 1을 더해줘서 다음 DFS함수의 for문에서 i가 tmp에서 겹치지 않게 하기위함
      }
    }
  };
  DFS(0, 1); //1부터 tmp에 들어가야하기 때문에 0,1로 시작

  return answer;
};

solution(4, 2);