[재귀]JavaScript로 순열과 조합 구현하기 (재귀 + 백트래킹)

프론트엔드 개발을 하다 보면, 순열(Permutation)과 조합(Combination)을 다뤄야 할 일이 종종 있습니다.
면접 준비나 알고리즘 문제 해결에 특히 자주 등장하죠.

이 글에서는 조합과 순열의 개념 차이부터,
JavaScript로 재귀 + 백트래킹을 활용한 구현 방법까지 정리해보겠습니다.

조합 (Combination)

서로 다른 n개의 원소 중에서 r개를 순서를 고려하지 않고 고르는 경우

예시로 [1, 2, 3, 4] 중 3개를 고르면:

[1,2,3], [1,2,4], [1,3,4], [2,3,4]

총 4가지 경우가 나옵니다.

💡 조합 구현 로직

조합은 다음처럼 동작합니다:

1. 배열을 순회하면서 fixed 값 고정
2. 고정된 값을 제외한 rest 배열 생성
3. rest 배열로 다시 조합 재귀 호출 (선택 개수 -1)
4. 재귀가 종료되면 결과를 하나씩 붙여가며 리턴

조합 구현 코드

const getCombination = (arr, selectNumber) => {
  const results = [];
  if (selectNumber === 1) return arr.map(el => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1); // 이후 요소들만
    const combinations = getCombination(rest, selectNumber - 1);
    const attached = combinations.map(comb => [fixed, ...comb]);
    results.push(...attached);
  });

  return results;
};

순열 (Permutation)

n개의 원소 중 r개를 순서를 고려하여 고르는 경우

예시로 [1, 2, 3] 중 2개를 고르면:

[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]

총 6가지 경우입니다.

💡 순열 구현 로직

조합과 비슷하지만, rest 배열의 구성 방식이 다릅니다:

• 조합: slice(index + 1) → 이후만 사용
• 순열: slice(0, index) + slice(index + 1) → 전체에서 fixed만 제외

순열 구현 코드

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

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map(per => [fixed, ...per]);
    results.push(...attached);
  });

  return results;
};

순열 vs 조합 정리표

마무리

순열과 조합은 단순한 개념 같지만, 구현에서는 작은 차이가 큰 영향을 미칩니다.
특히, 재귀 함수와 백트래킹의 기본 구조를 이해하는 데 아주 좋은 연습이 됩니다.

필요하다면 이 로직을 기반으로 중복 제거, 조건 필터링 등 확장된 문제에도 적용할 수 있어요.
연습 문제로 직접 구현해보는 걸 추천합니다 💪