백트래킹

[1, 2, 3]으로 만들 수 있는 순서(순열)를 전부 적어 봅니다. 지금까지 고른 값을 고른 것, 이미 쓴 값을 쓴 값으로 두고 손으로 따라갑니다.

이 리듬을 끝까지 돌리면 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 6개가 나옵니다. 4단계와 5단계처럼 되돌릴 때 쓴 값 표시도 같이 지워야 6단계에서 3을 다시 고를 수 있습니다. 이 한 줄을 빠뜨리는 것이 백트래킹 버그의 절반입니다.

백트래킹 코드는 문제가 달라져도 뼈대가 거의 같습니다. 위 순열을 그대로 코드로 옮겨 봅니다.

1. 완성 조건을 먼저 씁니다 — 다 골랐으면 기록하고 돌아옵니다. 이때 반드시 복사해서 넣습니다.

if (path.length === n) {
  result.push([...path]); // 복사본 — path는 계속 변하기 때문
  return;
}

2. 후보를 훑으면서 쓸 수 없는 것은 걸러냅니다.

for (let i = 0; i < n; i++) {
  if (used[i]) continue; // 이미 쓴 값은 건너뜀
}

3. 고릅니다 — 상태를 바꾸는 부분입니다.

used[i] = true;
path.push(items[i]);

4. 더 깊이 들어갑니다 — 자기 자신을 다시 호출합니다.

go();

5. 되돌립니다 — 3단계와 정확히 대칭이 되도록 원상 복구합니다.

path.pop();
used[i] = false;

전체 코드 — 순열 전부 만들기:

function solution(items: number[]): number[][] {
  const n = items.length;
  const result: number[][] = [];
  const path: number[] = [];
  const used = Array(n).fill(false);
 
  function go() {
    if (path.length === n) {      // 1단계: 완성 조건
      result.push([...path]);
      return;
    }
    for (let i = 0; i < n; i++) { // 2단계: 후보 제한
      if (used[i]) continue;
      used[i] = true;             // 3단계: 선택
      path.push(items[i]);
      go();                       // 4단계: 재귀
      path.pop();                 // 5단계: 되돌리기
      used[i] = false;
    }
  }
 
  go();
  return result;
}

• "가능한 모든 경우를 구하라", "조합을 전부 나열하라", "조건을 만족하는 배치를 찾아라" — 답이 하나의 값이 아니라 선택의 나열이면 이 유형입니다.
• 입력 크기가 유난히 작습니다. N ≤ 10(순열), N ≤ 20(부분집합) 수준의 제약은 "경우를 전부 시도해도 된다"는 출제자의 신호입니다.
• 대표 상황: 팀원 K명 뽑기(조합), 방문 순서 정하기(순열), 조건을 만족하는 부분집합 찾기, 퍼즐 배치(스도쿠·N-Queens류).
• 반대로 N이 크고 "최솟값 하나"만 물으면 DP나 그리디 쪽을 먼저 의심합니다.

뼈대는 항상 이 여섯 자리로 이루어집니다.

function solve(path: number[], used: boolean[], result: number[][]) {
  if (path.length === N) {          // ① 완성 조건
    result.push([...path]);          //    복사해서 저장 (참조 주의)
    return;
  }
  for (let i = 0; i < N; i++) {
    if (used[i]) continue;           // ② 후보 제한
    // if (가지치기 조건) continue;   // ③ 유망하지 않으면 스킵
    used[i] = true;
    path.push(items[i]);             // ④ 선택
    solve(path, used, result);       // ⑤ 재귀
    path.pop();                      // ⑥ 되돌리기 — ④와 정확히 대칭
    used[i] = false;
  }
}

무엇을 만드느냐에 따라 ②번 자리만 바뀝니다.

가지치기(③번 자리)에 자주 쓰는 조건들입니다.

• 합이 이미 목표를 초과 (음수가 없을 때) → 더 안 감
• 남은 것을 전부 더해도 목표 미달 → 더 안 감
• 조합(순서 무관)은 start 인덱스로 이전 것을 다시 안 봄 — 중복 조합 차단
• 정렬 후 같은 값 연속 스킵 — 중복 답 차단

• result.push(path) — 참조를 넣어 나중에 전부 같은(그리고 대개 빈) 배열이 됩니다. [...path]로 복사해야 합니다.

result.push(path);      // 잘못 — 이후 pop/push가 저장된 답까지 바꿈
result.push([...path]); // 고침 — 그 순간의 스냅샷을 저장

• 되돌리기 누락 또는 비대칭 — push했으면 반드시 pop, 표시했으면 반드시 해제합니다.

used[i] = true;
path.push(items[i]);
go();
path.pop();        // 잘못 — used[i] = false가 빠져 이후 가지에서 그 값을 못 씀

used[i] = true;
path.push(items[i]);
go();
path.pop();
used[i] = false;   // 고침 — 선택한 것을 하나도 빠짐없이 되돌림

• 조합 문제에 used 배열을 써서 같은 조합이 순서만 다르게 중복 생성됩니다. 조합은 start 인덱스로 제한합니다.

for (let i = 0; i < n; i++) if (!used[i]) { ... }  // 잘못 — [1,2]와 [2,1]이 따로 생김
for (let i = start; i < n; i++) { ... go(i + 1); } // 고침 — 뒤쪽만 보므로 중복 없음

• 가지치기 없이 N=20 완전탐색 → 시간 초과. 항상 "언제 포기할 수 있나"를 먼저 질문하세요.

• 가지치기가 실전과 완전탐색을 가릅니다. N이 15~20이면 부분집합은 2^20 ≈ 100만이라 아슬아슬하고, 순열은 20! 이라 손도 못 댑니다. 답이 될 가망이 없는 가지를 얼마나 일찍 자르느냐가 통과를 결정합니다. 가지치기는 정답을 바꾸지 않고 탐색량만 줄이므로, "이 가지에서는 절대 답이 나올 수 없다"가 증명 가능할 때만 잘라야 합니다.
• 되돌리기가 필요한 이유: 상태(path, used, 격자 표시)를 형제 가지끼리 공유하기 때문입니다. 매번 새 배열을 복사해 넘기면 되돌리기가 필요 없지만, 복사 비용이 가지 수만큼 붙습니다. 백트래킹은 "공유 + 되돌리기"로 이 비용을 없앤 방식입니다.
• 탐색 순서도 성능입니다. 후보를 정렬해 유망한 것부터 보면 좋은 답이 일찍 나오고, 그 답을 기준으로 이후 가지를 더 많이 자를 수 있습니다(분기 한정).
• 경계: "모든 경우를 시도하고 되돌아오기"에서 상태만 기록해 재사용하기 시작하면 DP이고, 되돌리기 없이 앞으로만 나아가면 DFS 탐색입니다. 세 유형은 같은 재귀 뼈대를 공유합니다.

시각화로 선택 → 깊이 → 되돌리기 리듬을 익힌 뒤, 부분집합 합 → 조합 → 제약이 있는 선택(가지치기 설계) 순으로 푸세요.