JavaScript로 배열의 모든 순열(Permutation) 생성하는 방법

서로 다른 정수로 이루어진 배열이 주어졌을 때, 배열에 포함된 숫자들의 가능한 모든 순열(permutation)을 반환해야 하는 문제를 생각해 볼 수 있습니다.

예를 들어, 입력 배열이 다음과 같다면 −

const arr = [1, 2, 3];

출력 결과는 아래와 같아야 합니다 −

const output = [
   [1,2,3],
   [1,3,2],
   [2,1,3],
   [2,3,1],
   [3,1,2],
   [3,2,1]
];

원소가 3개인 배열의 순열 개수는 3! = 6가지이며, 위 출력에서 확인할 수 있듯이 각 원소가 첫 번째 자리에 한 번씩 위치하면서 나머지 원소들이 뒤따르는 구조입니다.

재귀를 활용한 순열 생성 코드

이 문제는 재귀 함수를 사용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 이미 선택된 원소를 제외한 나머지 원소들을 하나씩 추가하며 재귀적으로 탐색하는 것입니다.

코드는 다음과 같습니다 −

const arr = [1, 2, 3];
const findPermutations = (arr = []) => {
   let res = []
   const helper = (arr2) => {
      if (arr2.length == arr.length)
      return res.push(arr2)
      for(let e of arr)
      if (!arr2.includes(e))
      helper([...arr2, e])
   };
   helper([])
   return res;
};
console.log(findPermutations(arr));

코드 동작 원리

• helper 함수는 현재까지 만들어진 부분 순열(arr2)을 인자로 받습니다.
• 부분 순열의 길이가 원본 배열과 같아지면 완성된 순열이므로 결과 배열 res에 저장합니다.
• 그렇지 않으면 원본 배열의 각 원소를 순회하면서, 아직 포함되지 않은 원소라면 새로운 배열에 추가하여 재귀 호출을 진행합니다.
• 스프레드 연산자([...arr2, e])를 사용하기 때문에 기존 배열이 변경되지 않고, 각 분기마다 독립적인 배열이 유지됩니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

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

시간 복잡도

n개의 서로 다른 원소를 가진 배열의 순열 개수는 n!이므로, 이 알고리즘의 시간 복잡도는 O(n × n!)입니다. 또한 includes 메서드가 배열을 선형 탐색하기 때문에 실제 실행 시간에는 추가적인 상수 요인이 붙습니다. 성능이 중요한 경우 방문 여부를 Set으로 관리하거나 백트래킹(backtracking) 기법으로 최적화할 수 있습니다.