data structures - 백트래킹(Backtracking)

백트래킹(Backtracking) 이란?

백트래킹은 주로 조합(combination) 및 순열(permutation)과 같은 문제를 해결하기 위한 알고리즘 기법 중 하나이다. 이 기법은 가능한 모든 해를 탐색하면서 원하는 해를 찾아내는 데 사용된다.

백트래킹의 개념:

백트래킹은 '퇴각 검색' 또는 '다시 돌아가기'라고도 한다
문제의 해를 찾을 때, 현재 시점에서 가능한 모든 후보를 확인하다가 더 이상 나아갈 수 없으면 이전 단계로 돌아가서 다른 후보를 탐색한다 이 과정을 반복하면서 최종적으로 원하는 해를 찾는다. 여기서 상당히 머리에 쥐가나기 시작한다
DFS도 재귀적으로 구현을 할수있고 백트래킹도 재귀적인개념인데 간단하게 말하면, DFS는 그래프 또는 트리를 탐색하는 일반적인 알고리즘이고, 백트래킹은 해를 찾아가면서 특정 제약 조건을 만족하는 경우에만 계속 진행하는 알고리즘 이다 DFS에 백트래킹이 포함되게 만들수도 있는데 이것은 좀더 공부를 해봐야할것같다.

function backtrackingCombination(arr, selected, start, M) {
  if (selected.length === M) {
    console.log(selected);
    return;
  }

  for (let i = start; i < arr.length; i++) {
    selected.push(arr[i]);
    backtrackingCombination(arr, selected, i + 1, M);
    selected.pop();  // 백트래킹: 이전 선택 상태로 돌아감
  }
}

const N = 5;  // 1부터 N까지의 자연수
const M = 3;  // 조합의 크기
const numbers = Array.from({ length: N }, (_, index) => index + 1);

backtrackingCombination(numbers, [], 0, M);