대부분의 경우 열거 문제는 재귀 열거로 해결됩니다. 안타깝게도 일반적인 접근 방식은 없습니다. 종종 반복 방법은 작업 자체에 크게 의존합니다.
그러나 다양한 조합 개체를 열거하는 방법 사이에서 약간의 유사성을 알 수 있습니다. 따라서 예시적인 예로 n에서 k까지의 모든 조합을 생성하는 코드를 고려하십시오.
정수 n, k;
// 조합 접두사를 지원하는 배열입니다.
//
// 이 경우 접두사는 조합에서 일부 개체를 선택했음을 의미합니다.
//
// 이후에 올바른 조합으로 완료되거나
// 또는 접두사가 올바르게 완료될 수 없음을 인식하면 재귀가 분기를 차단합니다.
vector 어러;
// 재귀 반복 함수 자체
//
// pos - 현재 순간에 결정할 객체의 조합 번호(0에서 k - 1까지)
//
// prev - 이전 단계에서 가져온 객체의 값
//
// 조합에서 객체의 순서는 중요하지 않습니다([1, 2]와 [2, 1]은 동일하고 유사한 것으로 간주됨),
// 따라서 객체 값이 오름차순인 세트만 생성하려고 합니다.
//
// [1, 2], [2, 1]과 같은 동일한 옵션이 한 번만 반복되도록 하기 위해 필요합니다.
// (이 경우 [1, 2]만 고려하고 [2, 1]은 순서 집합이 아니므로 고려하지 않음).
//
// 반복 횟수를 줄이기 위해 prev 변수를 유지하는 이유입니다.
무효 rec(int pos, int prev) {
// 선택한 요소의 수가 k이면 이미 모든 요소를 선택한 것입니다.
// 왜냐하면 숫자는 0에서 k - 1까지입니다.
경우 (pos == k) {
// 조건이 충족되면 이제 올바른 조합이 arr 배열에 있습니다.
// 어떻게든 처리할 수 있습니다(이 경우에는 콘솔에 출력합니다).
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' '
cout << '\n';
반품; // 재귀 분기를 잘라냅니다. 왜냐하면 이미 조합이 있고 더 이상 계속할 필요가 없습니다.
}
// 여기에서 나머지 요소에서 올바른 조합을 얻을 수 있는지 확인합니다.
// 남은 요소가 충분하지 않으면 이 재귀 분기를 잘라냅니다.
if (k - pos > n - prev - 1)
반품;
// 인덱스 pos로 위치에 놓은 객체를 반복합니다.
// 하지만 왜냐하면 순서가 있는 집합을 원하면 가능한 최소값은 prev + 1입니다.
for (int i = prev + 1; i < n; i++) {
arr.push_back(i); // 전역 배열에 요소를 추가합니다. 이제 우리는 그를 선택한 것 같습니다
rec(pos + 1, i); // 재귀적으로 실행하여 다음 항목을 설정합니다.
arr.pop_back(); // 재귀에서 돌아온 후 현재 선택한 요소는 더 이상 관련이 없습니다.
// 왜냐하면 재귀 내부에서 우리는 이러한 접두사를 사용하여 모든 옵션을 검토했습니다.
// 따라서 이 요소를 제거해야 합니다.
}
}
정수 메인()
{
cin>> n>> 케이;
// 처음에는 0번째 위치에 요소를 설정합니다.
// 요소 -1이 이전에 선택되었다고 가정하므로 처음에 null 객체에서 반복이 시작됩니다.
rec(0, -1);
0을 반환합니다.
}
같은 코드지만 주석이 없습니다:
정수 n, k;
vector 어러;
무효 rec(int pos, int prev) {
경우 (pos == k) {
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
반품;
}
if (k - pos > n - prev - 1)
반품;
for (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
정수 메인() {
cin>> n>> 케이;
rec(0, -1);
0을 반환합니다.
}
재귀 반복에서는 재귀 컷에 항상 특별한 주의를 기울여야 합니다. 실제로는 프로그램 속도를 크게 높일 수 있습니다.