이번 편의 결과물: coding-test/09-recursion-backtracking/에 재귀·백트래킹 문제 4개를 풀이 파일과 테스트로 완성합니다. · 다루는 개념: 재귀 호출 구조와 종료 조건, 백트래킹, 가지치기, 순열·조합 생성
이 편에서 만드는 파일
coding-test/09-recursion-backtracking/
├── 01-reverse-string/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-permutations/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-combinations/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-combination-sum/
├── solution.js (+)
└── solution.test.js (+)개념 정리
| 개념 | 설명 |
|---|---|
| 재귀 호출 | 함수가 실행 중에 자기 자신을 다시 호출하는 것 |
| 종료 조건(base case) | 재귀 호출을 멈추는 조건. 없으면 콜스택이 계속 쌓여 스택 오버플로가 난다 |
| 백트래킹 | 후보를 하나씩 선택해보다가 조건에 맞지 않으면 마지막 선택을 취소하고 되돌아가는 탐색 방식 |
| 가지치기(pruning) | 끝까지 가봐도 답이 될 수 없음이 확실한 branch는 아예 들어가지 않고 건너뛰는 최적화 |
재귀 함수는 항상 종료 조건을 먼저 쓴다. 종료 조건이 없거나 매 호출마다 인자가 실제로 줄어들지 않으면 무한히 자신을 호출해 콜스택이 넘칩니다.
백트래킹은 재귀로 “선택 → 재귀 → 선택 취소”를 반복하는 패턴입니다. 값을 push해 선택하고, 재귀 호출이 끝나면 pop으로 그 선택을 취소한 뒤 다음 후보를 시도합니다. 순열은 “이미 쓴 원소인지”만 확인하면 되고, 조합은 “이전 인덱스로 되돌아가지 않기”로 순서 중복을 막습니다.
실습
1. 문자열 뒤집기 — 재귀의 종료 조건
문제: 문자열 str을 받아 거꾸로 뒤집은 문자열을 반환하는 solution(str)을 재귀로 구현합니다.
입출력 예
| 입력 | 출력 |
|---|---|
"" | "" |
"a" | "a" |
"hello" | "olleh" |
접근(복잡도): 길이가 1 이하면 그대로 반환(종료 조건)하고, 아니면 “첫 글자를 뺀 나머지를 뒤집은 결과” 뒤에 첫 글자를 붙입니다. 호출마다 slice와 문자열 연결이 O(n)이고 호출이 n번 일어나 전체는 O(n²)입니다. 반복문이면 O(n)이지만, 여기 목적은 종료 조건 훈련입니다.
코드
// coding-test/09-recursion-backtracking/01-reverse-string/solution.js
// 시간복잡도: O(n^2) — 호출마다 slice와 문자열 연결에 O(n), 호출이 n번 일어난다
// 공간복잡도: O(n) — 재귀 호출 스택이 문자열 길이만큼 쌓인다
export function solution(str) {
if (str.length <= 1) {
return str;
}
return solution(str.slice(1)) + str[0];
}테스트
// coding-test/09-recursion-backtracking/01-reverse-string/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('빈 문자열은 그대로 반환한다', () => {
assert.strictEqual(solution(''), '');
});
test('한 글자 문자열은 그대로 반환한다', () => {
assert.strictEqual(solution('a'), 'a');
});
test('여러 글자 문자열을 뒤집는다', () => {
assert.strictEqual(solution('hello'), 'olleh');
});node --test 01-reverse-string/solution.test.js
# tests 3, pass 3, fail 0함정: str.length <= 1을 str.length === 0으로만 쓰면 한 글자 문자열에서도 재귀를 한 번 더 돌긴 하지만 결과는 맞습니다. 문제는 종료 조건 자체를 빼먹는 경우입니다. 그러면 빈 문자열에서 str[0]이 undefined가 되어 결과 문자열에 "undefined"가 섞입니다.
2. 순열 생성 — 백트래킹의 선택과 취소
문제: 정수 배열 nums의 모든 순열을 2차원 배열로 반환하는 solution(nums)를 구현합니다.
입출력 예
| 입력 | 출력(순서 무관) |
|---|---|
[1] | [[1]] |
[1, 2, 3] | [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 총 6개 |
접근(복잡도): 아직 쓰지 않은 원소를 하나 골라 current에 넣고 재귀로 다음 자리를 채운 뒤 pop으로 선택을 취소합니다. used 배열로 이미 고른 인덱스를 표시합니다. 길이 n인 순열은 n!개, 각각 완성에 O(n)이 걸려 전체는 O(n! * n)입니다.
코드
// coding-test/09-recursion-backtracking/02-permutations/solution.js
// 시간복잡도: O(n! * n) — 순열 n!개를 만들고 완성마다 배열 복사에 O(n)
// 공간복잡도: O(n! * n) — 만들어진 모든 순열을 result에 저장한다
export function solution(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
const current = [];
function backtrack() {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let i = 0; i < nums.length; i += 1) {
if (used[i]) continue;
used[i] = true;
current.push(nums[i]);
backtrack();
current.pop();
used[i] = false;
}
}
backtrack();
return result;
}테스트
// coding-test/09-recursion-backtracking/02-permutations/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
function sortResult(result) {
return result.map((row) => row.join(',')).sort();
}
test('원소 1개는 순열이 1개다', () => {
assert.deepStrictEqual(solution([1]), [[1]]);
});
test('원소 3개의 순열은 6개다', () => {
const result = solution([1, 2, 3]);
assert.strictEqual(result.length, 6);
});
test('모든 순열 조합이 정확히 만들어진다', () => {
const result = solution([1, 2, 3]);
assert.deepStrictEqual(sortResult(result), ['1,2,3', '1,3,2', '2,1,3', '2,3,1', '3,1,2', '3,2,1']);
});node --test 02-permutations/solution.test.js
# tests 3, pass 3, fail 0함정: current.push 다음에 current.pop()을 빼먹으면 이전 선택이 배열에 계속 남아 결과가 실제 순열보다 길어지거나 뒤섞입니다. used[i] = true 뒤에 used[i] = false로 되돌리는 것도 마찬가지로 반드시 짝을 맞춰야 합니다.
3. 조합 생성 — 순서 중복 막기
문제: 정수 배열 nums에서 r개를 고르는 모든 조합을 반환하는 solution(nums, r)을 구현합니다.
입출력 예
| 입력 | 출력 개수 |
|---|---|
nums=[1,2,3,4], r=2 | 6개([1,2], [1,3], [1,4], [2,3], [2,4], [3,4]) |
nums=[1,2], r=0 | 1개([]) |
접근(복잡도): 조합은 순서를 구분하지 않으므로 재귀 호출에 “다음엔 어디서부터 고를지”를 뜻하는 start 인덱스를 넘깁니다. 다음 호출에 i + 1을 넘겨 지나온 인덱스로 되돌아가지 않게 하면 중복이 생기지 않습니다. 개수는 C(n, r)개, 전체 시간은 O(C(n, r) * r)입니다.
코드
// coding-test/09-recursion-backtracking/03-combinations/solution.js
// 시간복잡도: O(C(n, r) * r) — 조합 개수만큼 만들고 완성마다 배열 복사에 O(r)
// 공간복잡도: O(C(n, r) * r) — 만들어진 모든 조합을 result에 저장한다
export function solution(nums, r) {
const result = [];
const current = [];
function backtrack(start) {
if (current.length === r) {
result.push([...current]);
return;
}
for (let i = start; i < nums.length; i += 1) {
current.push(nums[i]);
backtrack(i + 1);
current.pop();
}
}
backtrack(0);
return result;
}테스트
// coding-test/09-recursion-backtracking/03-combinations/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('4개 중 2개를 고르면 6가지다', () => {
const result = solution([1, 2, 3, 4], 2);
assert.strictEqual(result.length, 6);
});
test('고른 순서가 오름차순으로 유지된다', () => {
const result = solution([1, 2, 3, 4], 2);
assert.deepStrictEqual(result[0], [1, 2]);
});
test('r이 0이면 빈 배열 하나만 반환한다', () => {
const result = solution([1, 2], 0);
assert.deepStrictEqual(result, [[]]);
});node --test 03-combinations/solution.test.js
# tests 3, pass 3, fail 0함정: 다음 호출에 i + 1 대신 항상 0을 넘기면 순열처럼 순서를 구분하게 되어 같은 조합이 여러 번([1,2]와 [2,1]처럼) 나옵니다. 조합에서는 “이미 고려한 원소는 다시 앞에서 보지 않는다”가 핵심입니다.
4. 조합의 합 — 가지치기로 탐색 줄이기
문제: 서로 다른 양의 정수 배열 candidates와 target이 주어질 때, 후보를 몇 번이든 다시 사용해 합이 정확히 target이 되는 모든 조합을 반환하는 solution(candidates, target)을 구현합니다.
입출력 예
| 입력 | 출력 |
|---|---|
candidates=[2,3,6,7], target=7 | [[2,2,3],[7]] |
candidates=[2], target=4 | [[2,2]] |
candidates=[5], target=3 | [] |
접근(복잡도): candidates를 오름차순 정렬한 뒤 start부터 후보를 골라 remaining을 줄여갑니다. 같은 수를 다시 쓸 수 있어 다음 재귀엔 i를 그대로 넘깁니다. 정렬 덕분에 후보가 remaining보다 크면 뒤도 모두 크므로 즉시 멈춰(가지치기) 불필요한 탐색을 건너뜁니다.
코드
// coding-test/09-recursion-backtracking/04-combination-sum/solution.js
// 시간복잡도: 최악의 경우 지수적 — 후보를 반복 사용하며 가능한 조합을 탐색한다(가지치기로 실제 실행은 줄어든다)
// 공간복잡도: O(target / min(candidates)) — 재귀 깊이가 remaining이 줄어드는 만큼 쌓인다
export function solution(candidates, target) {
const sorted = [...candidates].sort((a, b) => a - b);
const result = [];
const current = [];
function backtrack(start, remaining) {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < sorted.length; i += 1) {
const candidate = sorted[i];
if (candidate > remaining) {
break;
}
current.push(candidate);
backtrack(i, remaining - candidate);
current.pop();
}
}
backtrack(0, target);
return result;
}테스트
// coding-test/09-recursion-backtracking/04-combination-sum/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('합이 7이 되는 조합을 모두 찾는다', () => {
const result = solution([2, 3, 6, 7], 7);
assert.deepStrictEqual(result, [[2, 2, 3], [7]]);
});
test('같은 수를 여러 번 사용할 수 있다', () => {
const result = solution([2], 4);
assert.deepStrictEqual(result, [[2, 2]]);
});
test('만들 수 있는 조합이 없으면 빈 배열이다', () => {
const result = solution([5], 3);
assert.deepStrictEqual(result, []);
});node --test 04-combination-sum/solution.test.js
# tests 3, pass 3, fail 0함정: 정렬을 빼먹고 break만 쓰면 정렬되지 않은 배열에서는 뒤에 더 작은 후보가 남아 있어도 건너뛰게 되어 정답을 놓칩니다. 가지치기용 break는 반드시 정렬 후에만 안전합니다.
직접 해보기
- 문제 1의
solution을 재귀 대신for반복문으로 다시 구현해,slice와 문자열 연결을 반복하지 않고 시간복잡도를O(n)으로 줄여보세요. - 문제 2의
solution을 변형해n개 중r개만 골라 순서를 구분해 나열하는partialPermutations(nums, r)을 만들어보세요.
정답 보기(2번)
문제 2의 solution 안 backtrack 함수와 거의 같지만 종료 조건을 current.length === nums.length 대신 current.length === r로 바꾸면 됩니다. 순서를 구분해야 하므로 used 배열로 중복 선택을 막는 부분은 그대로 둡니다.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| 재귀 호출 중 스택 오버플로 | 종료 조건이 없거나 인자가 실제로 줄어들지 않음 | 종료 조건을 함수 맨 앞에 쓰고, 재귀 인자가 매번 작아지는지 확인한다 |
| 순열 결과에 중복 원소가 섞임 | used 배열을 갱신하지 않거나 pop을 빼먹음 | push → 재귀 → pop → used 해제 순서를 항상 짝으로 맞춘다 |
| 조합에서 같은 조합이 여러 번 나옴 | 다음 호출에 항상 backtrack(0)을 넘겨 이전 인덱스를 다시 검사함 | 다음 호출에 i + 1을 넘겨 지나온 인덱스는 다시 보지 않는다 |
| 문제 4의 solution이 같은 조합을 두 번 반환함 | 정렬하지 않아 순서만 다른 같은 조합이 따로 생성됨 | candidates를 정렬한 뒤 시작 인덱스를 유지해 앞쪽 후보만 재사용하게 한다 |