Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.
Если в задаче вам необходимо проверить существование какой-либо перестановки или найти количество подходящих перестановок или что-то похожее, то стоит подумать о том, чтобы применить динамическое программирование по подмножествам.
Основным параметром будет являться битовая маска, которая будет показывать какие элементы уже были включены в перестановку, а какие нет. Также часто требуется второй параметр, который показывает, какой элемент был включен последним.
Часто перестановки можно увидеть в контексте путей в графах. Соответственно рассмотрим классический пример - задача о гамильтоновом пути.
Гамильтонов путь - это простой путь, проходящий через каждую вершину графа ровно один раз. Его можно представить просто как перестановку длины n, где n - количество вершин. Порядок внутри этой перестановки будет обозначать порядок обхода вершин в этом пути.
Для того, чтобы проверить наличие гамильтонова пути в графе, заведем динамику dp[mask][last] - существует ли простой путь, который обошел вершины, помеченные единицами в битовой маске mask и при этом закончил в вершине last.
Начальные значения будут dp[2i][i] = true, остальные false, что означает, что всегда есть пустой путь, начинающийся в любой из вершин.
Имея значение true в dp[mask][last] будем делать переходы вперед, по смыслу "продлевая путь". То есть будем искать номера вершин, которые помечены нулем в mask (мы их еще не посещали в пути) и при этом такие, что есть ребро из last в эту вершину (путь должен быть продлен существующим ребром). То есть делаем dp[mask | 2k][k] = true, если dp[mask][last] = true И mask & 2k = 0 (вершину k еще не посещали) И есть ребро last -> k.
В конечном итоге гамильтонов путь существует, если есть значение true в dp по параметрам битовой маски, состоящей только из единиц, и любой последней вершины.