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


Задача

1 /4


Все ПСП

Теория Нажмите, чтобы прочитать/скрыть

В большинстве случаев переборные задачи решаются посредством рекурсивных переборов. К сожалению, общего подхода не существует, т.к. зачастую методы перебора сильно зависят от самой задачи.
Однако можно заметить некую схожесть среди методов перебора различных комбинаторных объектов. Поэтому для показательного примера рассмотрим код, генерирующий все сочетания из 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;
}
 
В рекурсивных переборах всегда отдельное внимание стоит уделять отсечениям рекурсии. На практике они могут очень значительно ускорять работу программы.

Задача

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 8).

Выходные данные
Выведите все правильные скобочные последовательности по возрастанию в лексикографическом порядке. Каждую в отдельной строке.

 



Примеры
Входные данныеВыходные данные
1 3 ((()))
(()())
(())()
()(())
()()()

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6428
Java1
Python54
Комментарий учителя