완전 탐색은 가능한 후보를 빠짐없이 조사하여 조건을 만족하는 해를 찾는 방법이다. 입력 규모가 작을 때 기준 구현으로도 유용하다.
원리
후보를 생성하는 규칙과 검사 조건을 분리한다. 후보 수가 2ⁿ이나 n!처럼 늘어날 수 있으므로 입력 크기에 따른 전체 연산량을 먼저 추산한다.
예시
원소 4개의 부분집합은 16개이다. 각 부분집합의 합을 계산해 목표값과 비교하면 누락 없는 검사가 가능하다.
주의할 점
후보 생성 자체의 중복이나 누락을 검증해야 한다. 작은 입력에서 만든 완전 탐색 결과는 더 빠른 알고리즘의 테스트 기준으로 쓸 수 있다.