정수 배열을 입력받아 해당 원소들로 만들 수 있는 모든 순열(permutation)을 배열 형태로 반환하는 함수를 작성해 보겠습니다.
정수 배열을 인수로 받습니다 (예: [1, 2, 3, 4])
[1, 2, 3, 4]의 원소로 만들 수 있는 모든 순열을 담은 배열을 생성합니다
각 순열의 길이는 원본 배열의 길이(여기서는 4)와 동일해야 합니다
접근 방식: 백트래킹
이 문제는 백트래킹(backtracking) 기법으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열에서 원소를 하나씩 꺼내(
splice) 임시 배열(used)에 추가합니다. - 원본 배열이 모두 비면 하나의 순열이 완성된 것이므로, 결과 배열에 복사하여 저장합니다.
- 재귀 호출을 통해 나머지 원소들로 계속 순열을 확장해 나갑니다.
- 한 단계의 탐색이 끝나면 원소를 원래 위치에 되돌리고(
splice) 임시 배열에서도 제거하여(pop) 다음 경우의 수를 탐색합니다.
n개의 원소로 만들 수 있는 순열의 개수는 n!개이므로 시간 복잡도는 O(n!)입니다. 배열의 크기가 커질수록 결과의 수가 기하급수적으로 증가한다는 점을 유의해야 합니다.
예제 코드
전체 구현 코드는 다음과 같습니다.
const arr = [1, 2, 3, 4];
const permute = (arr = [], res = [], used = []) => {
let i, ch;
for (i = 0; i < arr.length; i++) {
ch = arr.splice(i, 1)[0];
used.push(ch);
if (arr.length === 0) {
res.push(used.slice());
}
permute(arr, res, used);
arr.splice(i, 0, ch);
used.pop();
};
return res;
};
console.log(permute(arr));실행 결과
콘솔에는 총 24개(4! = 24)의 순열이 출력됩니다.
[ [ 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 ] ]