🔵 백트래킹

완전 탐색의 한 종류... 가능한 모든 조합을 다 시도하는 것

부분수열의 합
요 문제를 예시로 설명해볼게에

0부터 N-1번째 원소까지 순서대로 방문할건데
방문마다 이번 원소를 포함시키거나 안시키거나 2가지 선택지를 탐색한다.

그렇게 탐색하면서 현재 합이 S가 될 때마다 전역변수 cnt를 증가시키면 cnt가 답이양. 밑에 그림으로 이해해보아

이렇게 DFS탐색을 해 가며 모든 정점을 다 방문한다!

여기서 중요한 점은, A번 정점의 DFS가 끝날 때마다 A번 정점을 방문하기 전 상태로 되돌려놔야 한다는 것이다.

참고로 위 문제의 시간복잡도는 O(2^N)

이렇게 가능한 모든 조합을 다 시도하는 것이 백트래킹이다.

💙 스터디 예제

◼ ch12-1 N과 M시리즈

15649 N과 M(1) ~ 15652 N과 M(4)
15654 N과 M(5) ~ 15657 N과 M(8)
15663 N과 M(9) ~ 15666N과 M(12)

◼ ch12-2

🔘II  1182 부분수열의 합
🟡IV 1987 알파벳
🟡V  9663 N-Queen
🟡IV 2580 스도쿠
🔘I   10597 순열장난