[ 논리적사고 ] - 재귀를 이용하여 부분 집합, 순열, 조합 구하기

📍 재귀를 이용하여 부분 집합, 순열, 조합 구하기

코딩테스트 문제를 풀다 보면 제목과 같이 부분집합(subSet), 순열(permutation), 조합(combination)을 구해야 하는일이 간혹 있다. 그때마다 코드를 구현하려니까 시간이 부족해서 다른 부분에 시간을 쏟지 못한 적이 있었다. 어떻게 구현해야 하는지 간단하게 알아보자. 

 

arr=[1, 2, 3, 4]로 예를 들어 나올 수 있는 경우의 수를 구해보는데, 모두 재귀(DFS)를 이용하여 구했다. 부분집합은 출력하는 모든 경우의 수를 구하고, 순열은 중복을 허용 / 허용하지 않고 일렬로 세우는 방법, 조합은 4개 중 2개를 뽑는 경우의 수로 가정해서 구했다. 이를 응용한 문제는 다음을 참고하자.

 

1. 부분집합: 부분집합 구하기, 바둑이 승차, 최대점수 구하기
2. 순열: 중복순열 구하기, 동전 교환, 순열 구하기
3. 조합: 조합의 경우의 수, 수열 추측하기, 조합 구하기

 

728x90

 

let n = 4;
let arr = [1, 2, 3, 4];

// 부분집합(subSet), 2^4=16

console.log(solution(n, arr));

function solution(n, arr){
  let temp = Array.from({length: n}, () => 0);
  function DFS(L){
    if (L === n){
      console.log(temp);
    }else{
      temp[L] = arr[L];
      DFS(L+1);
      temp[L] = 0;
      DFS(L+1)
    }
  }
  DFS(0)
}

👉🏽
[ 1, 2, 3, 4 ]
[ 1, 2, 3, 0 ]
[ 1, 2, 0, 4 ]
[ 1, 2, 0, 0 ]
[ 1, 0, 3, 4 ]
[ 1, 0, 3, 0 ]
[ 1, 0, 0, 4 ]
[ 1, 0, 0, 0 ]
[ 0, 2, 3, 4 ]
[ 0, 2, 3, 0 ]
[ 0, 2, 0, 4 ]
[ 0, 2, 0, 0 ]
[ 0, 0, 3, 4 ]
[ 0, 0, 3, 0 ]
[ 0, 0, 0, 4 ]
[ 0, 0, 0, 0 ]

// 순열(중복 허용 o), 4^4=256
function solution(n, arr){
  let temp = Array.from({length: n}, () => 0);
  function DFS(L){
    if (L === n){
      console.log(temp);
    }else{
      for (let i=0; i<n; i++){
        temp[L] = arr[i];
        DFS();
      }
    }
  }
  DFS(0)
}

👉🏽
[ 1, 1, 1, 1 ]
[ 1, 1, 1, 2 ]
[ 1, 1, 1, 3 ]
[ 1, 1, 1, 4 ]
[ 1, 1, 2, 1 ]
[ 1, 1, 2, 2 ]
[ 1, 1, 2, 3 ]
[ 1, 1, 2, 4 ]
[ 1, 1, 3, 1 ]
[ 1, 1, 3, 2 ]
[ 1, 1, 3, 3 ]
[ 1, 1, 3, 4 ]
[ 1, 1, 4, 1 ]
[ 1, 1, 4, 2 ]
[ 1, 1, 4, 3 ]
[ 1, 1, 4, 4 ]
[ 1, 2, 1, 1 ]
[ 1, 2, 1, 2 ]
[ 1, 2, 1, 3 ]
[ 1, 2, 1, 4 ]
[ 1, 2, 2, 1 ]
[ 1, 2, 2, 2 ]
[ 1, 2, 2, 3 ]
[ 1, 2, 2, 4 ]
[ 1, 2, 3, 1 ]
[ 1, 2, 3, 2 ]
[ 1, 2, 3, 3 ]
[ 1, 2, 3, 4 ]
[ 1, 2, 4, 1 ]
[ 1, 2, 4, 2 ]
[ 1, 2, 4, 3 ]
[ 1, 2, 4, 4 ]
[ 1, 3, 1, 1 ]
[ 1, 3, 1, 2 ]
[ 1, 3, 1, 3 ]
[ 1, 3, 1, 4 ]
[ 1, 3, 2, 1 ]
[ 1, 3, 2, 2 ]
[ 1, 3, 2, 3 ]
[ 1, 3, 2, 4 ]
[ 1, 3, 3, 1 ]
[ 1, 3, 3, 2 ]
[ 1, 3, 3, 3 ]
[ 1, 3, 3, 4 ]
[ 1, 3, 4, 1 ]
[ 1, 3, 4, 2 ]
[ 1, 3, 4, 3 ]
[ 1, 3, 4, 4 ]
[ 1, 4, 1, 1 ]
[ 1, 4, 1, 2 ]
[ 1, 4, 1, 3 ]
[ 1, 4, 1, 4 ]
[ 1, 4, 2, 1 ]
[ 1, 4, 2, 2 ]
[ 1, 4, 2, 3 ]
[ 1, 4, 2, 4 ]
[ 1, 4, 3, 1 ]
[ 1, 4, 3, 2 ]
[ 1, 4, 3, 3 ]
[ 1, 4, 3, 4 ]
[ 1, 4, 4, 1 ]
[ 1, 4, 4, 2 ]
[ 1, 4, 4, 3 ]
[ 1, 4, 4, 4 ]
[ 2, 1, 1, 1 ]
[ 2, 1, 1, 2 ]
[ 2, 1, 1, 3 ]
[ 2, 1, 1, 4 ]
[ 2, 1, 2, 1 ]
[ 2, 1, 2, 2 ]
[ 2, 1, 2, 3 ]
[ 2, 1, 2, 4 ]
[ 2, 1, 3, 1 ]
[ 2, 1, 3, 2 ]
[ 2, 1, 3, 3 ]
[ 2, 1, 3, 4 ]
[ 2, 1, 4, 1 ]
[ 2, 1, 4, 2 ]
[ 2, 1, 4, 3 ]
[ 2, 1, 4, 4 ]
[ 2, 2, 1, 1 ]
[ 2, 2, 1, 2 ]
[ 2, 2, 1, 3 ]
[ 2, 2, 1, 4 ]
[ 2, 2, 2, 1 ]
[ 2, 2, 2, 2 ]
[ 2, 2, 2, 3 ]
[ 2, 2, 2, 4 ]
[ 2, 2, 3, 1 ]
[ 2, 2, 3, 2 ]
[ 2, 2, 3, 3 ]
[ 2, 2, 3, 4 ]
[ 2, 2, 4, 1 ]
[ 2, 2, 4, 2 ]
[ 2, 2, 4, 3 ]
[ 2, 2, 4, 4 ]
[ 2, 3, 1, 1 ]
[ 2, 3, 1, 2 ]
[ 2, 3, 1, 3 ]
[ 2, 3, 1, 4 ]
[ 2, 3, 2, 1 ]
[ 2, 3, 2, 2 ]
[ 2, 3, 2, 3 ]
[ 2, 3, 2, 4 ]
[ 2, 3, 3, 1 ]
[ 2, 3, 3, 2 ]
[ 2, 3, 3, 3 ]
[ 2, 3, 3, 4 ]
[ 2, 3, 4, 1 ]
[ 2, 3, 4, 2 ]
[ 2, 3, 4, 3 ]
[ 2, 3, 4, 4 ]
[ 2, 4, 1, 1 ]
[ 2, 4, 1, 2 ]
[ 2, 4, 1, 3 ]
[ 2, 4, 1, 4 ]
[ 2, 4, 2, 1 ]
[ 2, 4, 2, 2 ]
[ 2, 4, 2, 3 ]
[ 2, 4, 2, 4 ]
[ 2, 4, 3, 1 ]
[ 2, 4, 3, 2 ]
[ 2, 4, 3, 3 ]
[ 2, 4, 3, 4 ]
[ 2, 4, 4, 1 ]
[ 2, 4, 4, 2 ]
[ 2, 4, 4, 3 ]
[ 2, 4, 4, 4 ]
[ 3, 1, 1, 1 ]
[ 3, 1, 1, 2 ]
[ 3, 1, 1, 3 ]
[ 3, 1, 1, 4 ]
[ 3, 1, 2, 1 ]
[ 3, 1, 2, 2 ]
[ 3, 1, 2, 3 ]
[ 3, 1, 2, 4 ]
[ 3, 1, 3, 1 ]
[ 3, 1, 3, 2 ]
[ 3, 1, 3, 3 ]
[ 3, 1, 3, 4 ]
[ 3, 1, 4, 1 ]
[ 3, 1, 4, 2 ]
[ 3, 1, 4, 3 ]
[ 3, 1, 4, 4 ]
[ 3, 2, 1, 1 ]
[ 3, 2, 1, 2 ]
[ 3, 2, 1, 3 ]
[ 3, 2, 1, 4 ]
[ 3, 2, 2, 1 ]
[ 3, 2, 2, 2 ]
[ 3, 2, 2, 3 ]
[ 3, 2, 2, 4 ]
[ 3, 2, 3, 1 ]
[ 3, 2, 3, 2 ]
[ 3, 2, 3, 3 ]
[ 3, 2, 3, 4 ]
[ 3, 2, 4, 1 ]
[ 3, 2, 4, 2 ]
[ 3, 2, 4, 3 ]
[ 3, 2, 4, 4 ]
[ 3, 3, 1, 1 ]
[ 3, 3, 1, 2 ]
[ 3, 3, 1, 3 ]
[ 3, 3, 1, 4 ]
[ 3, 3, 2, 1 ]
[ 3, 3, 2, 2 ]
[ 3, 3, 2, 3 ]
[ 3, 3, 2, 4 ]
[ 3, 3, 3, 1 ]
[ 3, 3, 3, 2 ]
[ 3, 3, 3, 3 ]
[ 3, 3, 3, 4 ]
[ 3, 3, 4, 1 ]
[ 3, 3, 4, 2 ]
[ 3, 3, 4, 3 ]
[ 3, 3, 4, 4 ]
[ 3, 4, 1, 1 ]
[ 3, 4, 1, 2 ]
[ 3, 4, 1, 3 ]
[ 3, 4, 1, 4 ]
[ 3, 4, 2, 1 ]
[ 3, 4, 2, 2 ]
[ 3, 4, 2, 3 ]
[ 3, 4, 2, 4 ]
[ 3, 4, 3, 1 ]
[ 3, 4, 3, 2 ]
[ 3, 4, 3, 3 ]
[ 3, 4, 3, 4 ]
[ 3, 4, 4, 1 ]
[ 3, 4, 4, 2 ]
[ 3, 4, 4, 3 ]
[ 3, 4, 4, 4 ]
[ 4, 1, 1, 1 ]
[ 4, 1, 1, 2 ]
[ 4, 1, 1, 3 ]
[ 4, 1, 1, 4 ]
[ 4, 1, 2, 1 ]
[ 4, 1, 2, 2 ]
[ 4, 1, 2, 3 ]
[ 4, 1, 2, 4 ]
[ 4, 1, 3, 1 ]
[ 4, 1, 3, 2 ]
[ 4, 1, 3, 3 ]
[ 4, 1, 3, 4 ]
[ 4, 1, 4, 1 ]
[ 4, 1, 4, 2 ]
[ 4, 1, 4, 3 ]
[ 4, 1, 4, 4 ]
[ 4, 2, 1, 1 ]
[ 4, 2, 1, 2 ]
[ 4, 2, 1, 3 ]
[ 4, 2, 1, 4 ]
[ 4, 2, 2, 1 ]
[ 4, 2, 2, 2 ]
[ 4, 2, 2, 3 ]
[ 4, 2, 2, 4 ]
[ 4, 2, 3, 1 ]
[ 4, 2, 3, 2 ]
[ 4, 2, 3, 3 ]
[ 4, 2, 3, 4 ]
[ 4, 2, 4, 1 ]
[ 4, 2, 4, 2 ]
[ 4, 2, 4, 3 ]
[ 4, 2, 4, 4 ]
[ 4, 3, 1, 1 ]
[ 4, 3, 1, 2 ]
[ 4, 3, 1, 3 ]
[ 4, 3, 1, 4 ]
[ 4, 3, 2, 1 ]
[ 4, 3, 2, 2 ]
[ 4, 3, 2, 3 ]
[ 4, 3, 2, 4 ]
[ 4, 3, 3, 1 ]
[ 4, 3, 3, 2 ]
[ 4, 3, 3, 3 ]
[ 4, 3, 3, 4 ]
[ 4, 3, 4, 1 ]
[ 4, 3, 4, 2 ]
[ 4, 3, 4, 3 ]
[ 4, 3, 4, 4 ]
[ 4, 4, 1, 1 ]
[ 4, 4, 1, 2 ]
[ 4, 4, 1, 3 ]
[ 4, 4, 1, 4 ]
[ 4, 4, 2, 1 ]
[ 4, 4, 2, 2 ]
[ 4, 4, 2, 3 ]
[ 4, 4, 2, 4 ]
[ 4, 4, 3, 1 ]
[ 4, 4, 3, 2 ]
[ 4, 4, 3, 3 ]
[ 4, 4, 3, 4 ]
[ 4, 4, 4, 1 ]
[ 4, 4, 4, 2 ]
[ 4, 4, 4, 3 ]
[ 4, 4, 4, 4 ]

// 순열(중복 허용 x) 4x3x2x1=24
let n = 4;
let arr = [1, 2, 3, 4]

console.log(solution(arr));

function solution(arr){
  let temp = Array.from({length: n}, () => 0);
  let visited = Array.from({length: n}, () => 0);
  let cnt=0;

  function DFS(L){
    if (L === n){
      cnt++
      console.log(temp);
    }else{
      for (let i=0; i<n; i++){
        if (visited[i] === 0){
          visited[i] = 1;
          temp[L] = arr[i];
          DFS(L+1);
          visited[i] = 0;

        }
      }
    }
  }
  DFS(0)
  console.log(cnt)
}

👉🏽
[ 1, 2, 3, 4 ]
[ 1, 2, 4, 3 ]
[ 1, 3, 2, 4 ]
[ 1, 3, 4, 2 ]
[ 1, 4, 2, 3 ]
[ 1, 4, 3, 2 ]
[ 2, 1, 3, 4 ]
[ 2, 1, 4, 3 ]
[ 2, 3, 1, 4 ]
[ 2, 3, 4, 1 ]
[ 2, 4, 1, 3 ]
[ 2, 4, 3, 1 ]
[ 3, 1, 2, 4 ]
[ 3, 1, 4, 2 ]
[ 3, 2, 1, 4 ]
[ 3, 2, 4, 1 ]
[ 3, 4, 1, 2 ]
[ 3, 4, 2, 1 ]
[ 4, 1, 2, 3 ]
[ 4, 1, 3, 2 ]
[ 4, 2, 1, 3 ]
[ 4, 2, 3, 1 ]
[ 4, 3, 1, 2 ]
[ 4, 3, 2, 1 ]
24

// 조합(4개 중 2개를 뽑는 경우의 수), 4C2=6
let n = 4;
let m = 2;
let arr = [1, 2, 3, 4]

console.log(solution(n, arr));

function solution(n, arr){
  let temp = Array.from({length: m}, () => 0);
  let cnt=0;

  function DFS(L, S){
    if (L === m){
      cnt++
      console.log(temp);
    }else{
      for (let i=S; i<n; i++){
        temp[L] = arr[i];
        DFS(L+1, i+1);
      }
    }
  }
  DFS(0, 0)
  console.log(cnt)
}

👉🏽
[ 1, 2 ]
[ 1, 3 ]
[ 1, 4 ]
[ 2, 3 ]
[ 2, 4 ]
[ 3, 4 ]
6