[JS] 재귀 함수 3 - 순열, 조합

✨ 순열과 조합

순열과 조합은 코딩테스트에서 자주 나오지만 자바스크립트에서 제공해주는 built-in 함수가 없기때문에 직접 구현해야한다.

성능이나 콜 스택 위험으로 인해 스택으로 구현하는 것이 좋지만, 순열과 조합 자체가 시간복잡도가 굉장히 크기때문에 n이 크게 나오는 경우가 많지 않다.

따라서 재귀로 외우는 것이 직관적으로 편하다.

 

1. 순열

시간복잡도 O(n!)

function permutations(arr, n) {
  // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  arr.forEach((fixed, idx, arr) => {
    // 현재 index를 제외한 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.filter((_, index) => index !== idx);
    // 선택된 요소를 제외하고 재귀 호출한다.
    const perms = permutations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 순열을 합쳐준다.
    const combine = perms.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  return result;
}

 

2. 조합

시간복잡도 O(2^n)

function combinations(arr, n) {
  // 1개만 뽑는다면 그대로 조합을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  const result = [];

  arr.forEach((fixed, idx, arr) => {
    // 현재 index 이후 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.slice(idx + 1);
    // 선택된 요소 이전 요소들을 제외하고 재귀 호출한다.
    const combis = combinations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 조합을 합쳐준다.
    const combine = combis.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  return result;
}