Модуль: Рекурсивный перебор

В большинстве случаев переборные задачи решаются посредством рекурсивных переборов. К сожалению, общего подхода не существует, т.к. зачастую методы перебора сильно зависят от самой задачи.
Однако можно заметить некую схожесть среди методов перебора различных комбинаторных объектов. Поэтому для показательного примера рассмотрим код, генерирующий все сочетания из n по k.
 

int n, k;

// Массив, в котором поддерживаются префиксы сочетаний.
// Префикс в данном случае означает, что мы выбрали какие то объекты в сочетания.
// В последствии они либо достроятся в корректное сочетание, 
// либо рекурсия обрубит ветку, когда поймет, что такой префикс не сможет правильно достроиться
vector  arr; 


// самая функция рекурсивного перебора
// 
// pos - номер объекта в сочетании, который будем определять в текущий момент (от 0 до k - 1)
// prev - значение объекта, который взяли на предыдущем шаге
// 
// В сочетаниях порядок объектов не важен ([1, 2] и [2, 1] считаются одинаковыми и аналогично),
// поэтому мы хотим генерировать только такие наборы, где значения объектов идут по возрастанию.
// 
// Это нужно, чтобы одинаковые варианты такие как [1, 2] и [2, 1] перебирались только один раз
// (в нашем случае мы рассмотрим только [1, 2], а [2, 1] нет, т.к. это не упорядоченный набор).
// 
// Именно поэтому мы и храним переменную prev, чтобы сократить количество перебираемых вариантов

void rec(int pos, int prev) {
	// если номер выбираемого элемента равен k, то мы уже выбрали все элементы
	// т.к. их номера от 0 до k - 1
	if (pos == k) {
		
		// если условие выполнилось, то значит сейчас в массиве arr корректное сочетание
		// и мы можем его как то обработать (в данном случае просто вывести его в консоль)
		for (int i = 0; i < k; i++)
			cout << arr[i] + 1 << ' ';
		cout << '\n';
		return; // обрубаем ветку рекурсии, т.к. уже получили сочетание и дальше продолжать не надо
	}

	// здесь мы проверяем сможем ли мы из оставшихся элементов добрать корректное сочетание
	// если оставшихся элементов не хватает, то обрубаем эту ветку рекурсии
	if (k - pos > n - prev - 1)
		return;

	// перебираем объект, который поставим на позицию с индексом pos
	// но т.к. мы хотим упорядоченный набор, то минимальное возможно значение - prev + 1
	for (int i = prev + 1; i < n; i++) {

		arr.push_back(i); // Добавляем элемент в глобальный массив. Теперь мы как будто его выбрали

		rec(pos + 1, i); // запускаемся рекурсивно, чтобы установить следующие элементы

		arr.pop_back(); // после возвращения из рекурсии наш текущий выбранный элемент уже не актуален,
		                // т.к. внутри рекурсии мы перебрали все варианты с таким префиксом,
		                // поэтому этот элемент нужно удалить
	}
}

int main()
{
	cin >> n >> k;

	// изначально будем устанавливать элемент на 0-ой позиции
	// считаем, что до этого был выбран элемент -1, чтобы изначально перебор начинался с нулевого объекта
	rec(0, -1);

    return 0;
}

int n, k;
vector  arr;

void rec(int pos, int prev) {
	if (pos == k) {
		for (int i = 0; i < k; i++)
			cout << arr[i] + 1 << ' ';
		cout << '\n';
		return;
	}

	if (k - pos > n - prev - 1)
		return;
	for (int i = prev + 1; i < n; i++) {
		arr.push_back(i);
		rec(pos + 1, i);
		arr.pop_back();
	}
}


int main() {
	cin >> n >> k;
	rec(0, -1);

	return 0;
}