백트래킹 (Backtracking)

가능한 모든 경우의 수를 재귀적으로 탐색하면서, 조건에 맞지 않는 경로는 조기에 탐색을 중단(가지치기)하는 알고리즘

완전 탐색의 일종이지만, 불필요한 분기를 줄여 효율적으로 해결

• 보통 DFS(깊이 우선 탐색) 기반으로 구현됨
• 조건을 만족하지 않으면 "되돌아가기" (Backtrack) 수행
• 조합/순열/경로/문자열 생성 등 경우의 수 탐색 문제에 강력

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • O(k^n): 각 단계마다 k개의 선택지, n단계 → 최악의 경우
  • *가지치기(pruning)**로 탐색 공간을 줄일 수 있음
• 공간 복잡도
  • O(n): 재귀 호출 깊이 및 상태 저장 공간 (경로 배열 등)

구현 코드(조합)

const combine = (n, k) => {
  const result = [];

  const backtrack = (start, path) => {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop(); // 백트래킹
    }
  };

  backtrack(1, []);
  return result;
};

console.log(combine(4, 2));
// 출력: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

대표 문제 유형 및 핵심

문제	키워드	상태 표현	주요 로직	가지치기 조건	종료 조건
N-Queen	체스판 / 공격 범위	행, 열, 대각선	열/대각선 체크 배열 사용	같은 열/대각선일 경우 skip	모든 행 채움
순열	순서 있는 조합	visited[], path	visited[]로 중복 방지	이미 방문한 값 skip	path.length === n
조합	n개 중 r개 선택	시작 인덱스, path	i부터 반복, i+1로 재귀	중복 조합 방지	path.length === r
부분 집합	포함 / 비포함	인덱스, path	포함 / 비포함 2분기	없음	인덱스 === n
문자열 분해	회문, 조건부 분할	start index, path	유효한 조각일 때만 재귀	유효하지 않은 조각 제외	문자열 끝 도달
숫자 조합	target 합	누적합, path	누적합 계산하며 탐색	누적합 > target일 경우 return	누적합 === target