Выведите все уникальные комбинации расстановки N фишек на доске NxN.

Опубликовано: 21 Сентября, 2022

Для заданного целого числа N задача состоит в том, чтобы напечатать все уникальные комбинации размещения N фигур на доске NxN .

Примечание. Печатайте («*») для фигур и («-») для пустого места.

Пример:

Input: N = 2
Output:
* *
– –

* –
* –

* –
– *

– *
* –

– *
– *

– –
* *
Explanation: The total number of empty spaces are 2*2=4 and the pieces to be set is 2 so there are 4C2 combinations ((4!/(2!*2!))=6) possible which is represented above.

Input: N = 1
Output: *

Подход: Эту проблему можно решить, используя рекурсию для генерации всех возможных решений. Теперь выполните следующие действия, чтобы решить эту проблему:

  1. Создайте функцию с именем allCombinations , которая будет генерировать все возможные решения.
  2. Требуется целое число piecePlaced, обозначающее общее количество размещенных фигур, целое число N , обозначающее количество фигур, которые необходимо разместить, два целых числа row и col , обозначающие строку и столбец, в которые будет помещена текущая фигура, и строка ans для хранение матрицы, в которой размещены фигуры, в качестве аргументов.
  3. Теперь первоначальный вызов allCombinations будет передавать 0 как piecePlaced , N , 0 и 0 как строку и столбец и пустую строку как ans .
  4. В каждом вызове проверяйте базовый случай, то есть:
    • Если ряд становится N и все фигуры размещены, т.е. piecePlaced=N . Затем распечатайте ответ и вернитесь. В противном случае, если piecePlaced не N , просто вернитесь из этого вызова.
  5. Теперь сделайте два вызова:
    • Один, чтобы добавить «*» в текущую позицию, и один, чтобы покинуть эту позицию и добавить «-» .
  6. После этого рекурсивные вызовы будут печатать все возможные решения.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(2^M), где M=N*N
Вспомогательное пространство:

РЕКОМЕНДУЕМЫЕ СТАТЬИ