알고리즘 문제를 풀다보면 완전탐색으로 해결해야 하는 문제들이 있다.
완전탐색은 단어 그대로, 생길 수 있는 모든 경우의 수에 대해서 조건이 성립하는 지를 알아보는 것 자체를 말한다.
순열과 조합을 사용해서, 완전탐색을 할 대상에 대해 자료형을 구축해보자.

기본 규칙
순열, 조합, 중복순열 모두 같은 로직으로 진행된다.

배열에서 3개를 선택하는 경우를 생각해보자.
1. 하나의 수를 먼저 선택(고정)한다.
2. 나머지 2개를 선택한다.
3. 남는 배열에서 1개를 선택할 때까지(재귀 탈출 조건) 2번 과정을 재귀적으로 반복한다.

순열, 조합, 중복순열들은 서로 남은 나머지 배열을 설정해주는 과정에서만 차이가 있다.

Combination

조합은 서로 다른 n개의 원소 중에서 순서를 생각하지 않고 r개를 뽑는 것을 말한다. (중복X)

4Combination3 = 4C3을 코드로 구현해보자.

Input : [a, b, c, d]
Output : [ [a, b, c], [a, b, d], [a, c, d], [b, c, d] ]

4C3은 4개 중에 3개를 뽑을 때 나올 수 있는 모든 조합을 구한다는 것이다.
조합의 순서는 상관없다.
[a, b, c] = [c, b, a] 이처럼 순서가 바뀌어도 같은 구성이기 때문에 하나의 조합으로 취급한다.

시작
  a를 고정하고 -> 나머지 [b, c, d] 중에서 2개씩 조합을 구한다.
  [a, b, c] [a, b, d] [a, c, d]
  b를 고정하고 -> 나머지 [c, d] 중에서 2개씩 조합을 구한다.
  [b, c, d]
  c를 고정하고 -> 나머지 [d] 중에서 2개씩 조합을 구한다. 
  [] 
  d를 고정하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
  []
종료

아무리 들어오는 인풋의 배열이 길어진다고 해도, 위의 과정은 변하지 않는다.
배열의 처음부터 하나씩 고정한 후, 뒤의 나머지 배열에 대해서 조합을 구해서 붙이면 된다.
나머지에 대해서 조합을 구할때는 재귀(Recursion)함수를 사용하자 !
계속해서 반복될 일에 대해서 한번만 명시하고, 들어가는 인자(나를 뺀 나머지)를 바꾸어 주기만 하면 되기 때문이다.

구현

• 재귀 종료(탈출) 조건 : 하나를 선택할 때에는, 모든 배열의 원소를 선택해서 리턴한다.
• forEach문으로 배열의 모든 원소를 처음부터 끝까지 한 번씩 고정(fixed) 되도록 한다.
• 고정(fixed)된 값의 나머지 배열에 대해서 조합을 구하도록 한다.
  이 때, 선택하는 개수를 하나 줄인다.
• 조합을 만들어온 결과에 고정(fixed)된 값을 앞에 붙여서 리턴할 배열에 spread syntax로 배열화 한 후에 리턴한다.
• 2C3, 1C2 같이 선택하려는 개수가 더 많으면 빈 배열이 return되기 때문에 위의 예에서 3과 4를 선택할 때에는 빈 배열이 돌아와서 최종 결과값에 포함되지 않는다.

선택했던 것들이 다시 중복되면 안되기 때문에 rest 배열이 fixed 이후의 범위로 좁혀지면 안된다

const getCombinations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); 
  // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    // 해당하는 fixed를 제외한 나머지 뒤
    const rest = origin.slice(index + 1); 
    // 나머지에 대해서 조합을 구한다.
    const combinations = getCombinations(rest, selectNumber - 1); 
    //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
    const attached = combinations.map((combi) => [fixed, ...combi]); 
    // 배열 spread syntax 로 모두다 push
    results.push(...attached); 
  });
  
  // 결과 담긴 results return
  return results; 
}

Permutation

순열은 n개 중에 r개를 뽑아서 순서대로 나열하는 것을 말한다.
순열은, 조합에서 확장된 개념이기 때문에 조합을 이해하고 나면 쉬워진다.
조합은 순서에 상관없이 선택한 것이라면, 순열은 순서가 중요하다.

Input : [1, 2, 3, 4]
Output : [
   [ 1, 2, 3 ], [ 1, 2, 4 ],
   [ 1, 3, 2 ], [ 1, 3, 4 ],
   [ 1, 4, 2 ], [ 1, 4, 3 ],
   [ 2, 1, 3 ], [ 2, 1, 4 ],
   [ 2, 3, 1 ], [ 2, 3, 4 ],
   [ 2, 4, 1 ], [ 2, 4, 3 ],
   [ 3, 1, 2 ], [ 3, 1, 4 ],
   [ 3, 2, 1 ], [ 3, 2, 4 ],
   [ 3, 4, 1 ], [ 3, 4, 2 ],
   [ 4, 1, 2 ], [ 4, 1, 3 ],
   [ 4, 2, 1 ], [ 4, 2, 3 ],
   [ 4, 3, 1 ], [ 4, 3, 2 ]
 ]

구현

먼저, 재귀의 종료 조건은 조합을 구하는 함수와 동일하다.
한 개씩 선택한다고 하면 순서가 의미가 없어지기 때문이다.

[1, 2, 3, 4]에서 3개를 선택해서 순열을 만드는 코드의 내부를 수도코드로 적어보면 다음과 같다.
1, 2, 3, 4를 각각 순서대로 고정하고 나머지 요소만으로 이루어진 배열에서 (selectNumber - 1)만큼을 선택하여 또 순열을 구한다.(재귀)

1(fixed) => permutation([2, 3, 4]) => 2(fixed) => permutation([3, 4]) => ...
2(fixed) => permutation([1, 3, 4]) => 1(fixed) => permutation([3, 4]) => ...
3(fixed) => permutation([1, 2, 4]) => ...
4(fixed) => permutation([1, 2, 3]) => ...

아래의 코드를 살펴보면 정확히 다른 부분은 동일하고 배열의 나머지를 구하는 코드만 바뀌었음을 알 수 있다.

const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]
// 해당하는 fixed를 제외한 나머지 배열

const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); 
  // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
    // 해당하는 fixed를 제외한 나머지 배열 
    const permutations = getPermutations(rest, selectNumber - 1); 
    // 나머지에 대해 순열을 구한다.
    const attached = permutations.map((permu) => [fixed, ...permu]); 
    // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    results.push(...attached); 
    // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};

permutation with repetition

중복순열은 현재 fixed까지 다시 선택할 수 있기 때문에 rest배열이 매번 기본 arr이면 된다.
기본 arr는 forEach구문의 3번째 인자를 활용하자.

const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); 

  arr.forEach((fixed, index, origin) => {
    const rest = origin; 
    // 일반 순열 알고리즘과 차이점은 여기 한줄.
    const permutations = getPermutations(rest, selectNumber - 1); 
    const attached = permutations.map((permu) => [fixed, ...permu]); 
    results.push(...attached); 
    // 배열 spread syntax 로 모두다 push
  });

  return results;
};