백트래킹(Backtracking)

: 문제를 해결하는 과정에서 해의 후보군을 구성하고, 그 후보군이 조건을 만족하지 않으면 되돌아가(백트랙) 다른 경로를 탐색하는 방법이다.

• 재귀 알고리즘의 한 종류이다.
• 주로 조합 문제나 경로 탐색 문제에 많이 사용된다.

백트래킹의 핵심 개념

1. 해의 후보군 구성: 문제의 가능한 모든 경우를 탐색하기 위해, 부분해(문제의 일부분을 해결한 상태)들을 구성해 나간다.
2. 유망성 판단: 현재 선택한 부분해가 문제의 조건을 만족하는지 검사한다. 만족하지 않는다면 그 이후의 경로는 더 이상 탐색하지 않고, 다른 경로로 되돌아가(백트랙) 탐색을 이어나간다.
3. 완전한 해 도출: 유망한 부분해들을 모아서 문제의 최종적인 해를 찾는다.

백트래킹의 구조

1. 문제의 해를 찾기 위해 후보군을 구성한다.
2. 현재 후보군이 문제의 해가 될 수 있는지 확인한다.
   • 조건을 만족하지 않으면 그 경로는 더 이상 탐색하지 않고 되돌아간다(백트래킹).
3. 조건을 만족하면, 해를 찾기 위해 더 깊이 탐색한다.
4. 완전한 해를 찾으면 그 해를 반환하고, 아니라면 다른 경로를 탐색한다.

구현 코드

function findSubsets(nums) {
  const result = [];

  // 백트래킹 함수: 현재 선택된 요소들을 추적하는 `path`와 탐색할 시작 인덱스 `start`
  function backtrack(start, path) {
    // 현재 경로를 결과에 추가 (부분 집합의 하나)
    result.push([...path]);

    // 남은 요소들을 하나씩 탐색
    for (let i = start; i < nums.length; i++) {
      // 현재 숫자를 경로에 추가
      path.push(nums[i]);
      // 다음 숫자로 재귀 호출
      backtrack(i + 1, path);
      // 백트래킹: 경로에서 마지막 숫자를 제거
      path.pop();
    }
  }

  // 빈 경로로 시작하여 백트래킹 시작
  backtrack(0, []);
  
  return result;
}

// 사용 예시
const nums = [1, 2, 3];
console.log(findSubsets(nums));