개요
문자열 배열을 인수로 받아, 배열에 포함된 요소들로 만들 수 있는 모든 조합(순열)을 생성해 반환하는 JavaScript 함수를 작성해 보겠습니다. 예를 들어 ['a', 'b', 'c', 'd']라는 배열이 주어지면, 길이가 4인 순열부터 길이가 1인 경우까지 가능한 모든 문자열 조합을 결과로 얻어야 합니다.
접근 방식
이 문제는 재귀 호출과 백트래킹(backtracking) 기법으로 해결하는 것이 가장 효율적입니다. 핵심 아이디어는 다음과 같습니다.
- 각 재귀 단계에서 아직 사용되지 않은 요소를 하나씩 선택합니다.
- 선택한 요소는 불리언(boolean) 배열에 표시하여 같은 요소가 중복 선택되지 않도록 합니다.
- 배열로 사용 여부를 관리하면 별도의 탐색 없이 O(1) 시간에 중복을 확인할 수 있습니다.
- 목표 길이에 도달하면 현재까지 만든 문자열을 결과 배열에 저장하고, 백트래킹으로 선택을 되돌려 다른 경우를 계속 탐색합니다.
예제 코드
const arr = ['a', 'b', 'c', 'd'];
let res = [];
const permutations = (len, val, existing) => {
// 목표 길이에 도달하면 완성된 조합을 결과에 저장
if (len === 0) {
res.push(val);
return;
}
for (let i = 0; i < arr.length; i++) {
// 아직 사용하지 않은 요소만 선택
// existing 배열을 사용하면 O(1) 연산으로 중복 여부 확인 가능
if (!existing[i]) {
existing[i] = true; // 사용 표시
permutations(len - 1, val + arr[i], existing);
existing[i] = false; // 백트래킹: 선택 되돌리기
}
}
};
const buildPermutations = (arr = []) => {
// 길이가 n, n-1, ..., 1인 모든 순열을 차례로 생성
for (let i = 0; i < arr.length; i++) {
permutations(arr.length - i, "", []);
}
};
buildPermutations(arr);
console.log(res);
코드 설명
- permutations(len, val, existing): len은 앞으로 채워야 할 자릿수, val은 지금까지 만든 문자열, existing은 각 요소의 사용 여부를 저장하는 배열입니다.
- buildPermutations(arr): 전체 길이(n)부터 1까지 각 길이별 순열 생성을 시작하는 진입점 역할을 합니다.
실행 결과
위 코드를 실행하면 콘솔에 길이 4부터 1까지의 모든 순열이 다음과 같이 출력됩니다.
[ 'abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba', 'abc', 'abd', 'acb', 'acd', 'adb', 'adc', 'bac', 'bad', 'bca', 'bcd', 'bda', 'bdc', 'cab', 'cad', 'cba', 'cbd', 'cda', 'cdb', 'dab', 'dac', 'dba', 'dbc', 'dca', 'dcb', 'ab', 'ac', 'ad', 'ba', 'bc', 'bd', 'ca', 'cb', 'cd', 'da', 'db', 'dc', 'a', 'b', 'c', 'd' ]
시간 복잡도
n개의 서로 다른 요소에서 길이 k인 순열의 개수는 n!/(n-k)!이므로, 전체 결과 개수는 k=1부터 n까지의 합에 비례합니다. 따라서 전체 시간 복잡도는 대략 O(n × n!) 수준이며, n이 커질수록 결과 개수가 폭발적으로 증가하기 때문에 이 방식은 입력 크기가 작은 경우에 적합합니다.