현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

📍 상태 공간 트리
: 문제 해결 과정의 중간 상태들을 모두 노드로 나타내는 트리

예시 문제

1) N과 M (1)

https://www.acmicpc.net/problem/15649

• 후보군을 다 살펴보다가 더 이상 살펴볼 후보군이 없으면 그 전 단계로 되돌아가기
• 재귀 사용
• 💻 코드 참고

2) N-Queen

https://www.acmicpc.net/problem/9663

• 되돌아가면서 모든 후보군을 다 탐색하면, 아래와 같아진다.

• 💻 코드 참고

3) 부분수열의 합

https://www.acmicpc.net/problem/1182

• 위에 있는 두 개의 예제와 달리 선택해야 하는 숫자의 개수가 정해져있는 것이 아니므로 총합을 기준으로 재귀를 돌리기
• 부분수열에는 공집합도 포함됨을 기억
• 💻 코드 참고

STL next_permutation

• 현재 수열을 사전 순으로 했을 때 다음 수열을 만들고 true 반환
• 다음 수열이 존재하지 않으면 false 반환
• 반복문을 돌기 전에 반드시 오름차순 정렬 필요❗️

• #include <algorithm>

## 1) 순열
```cpp
int a[3] = {1, 2, 3};
do {
	for (int i = 0; i < 3; i++)
    {
    	cout << a[i];
    }
    cout << '\n';
} while (next_permutation(a, a+3));

// 결과 값은 아래와 같다.
/*
123
132
213
231
312
321
*/

2) 조합

int a[4] = {0, 0, 1, 1};
do {
	for (int i = 0; i < 4; i++)
    {
    	if (a[i] == 0)
        	cout << i + 1;
    }
    cout << '\n';
} while (next_permutation(a, a+4));

// 결과 값은 아래와 같다.
/*
12
13
14
23
24
34
*/