Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.
If you need to check the existence of a permutation in a problem, or find the number of permutations that match, or something similar, then you should consider using dynamic subset programming.
The main parameter will be a bitmask, which will show which elements have already been included in the permutation, and which are not. Also often required is a second parameter that indicates which element was included last.
Often permutations can be seen in the context of paths in graphs. Accordingly, let us consider a classical example - the Hamiltonian path problem.
A Hamiltonian path is a simple path that passes through each vertex of the graph exactly once. It can be represented simply as a permutation of length n, where n is the number of vertices. The order within this permutation will indicate the order in which the vertices in this path are traversed.
In order to check the presence of a Hamiltonian path in the graph, let's start the dynamics dp[mask][last] - is there a simple path that bypassed the vertices marked with ones in the mask bitmask and ended up at the last vertex.
The initial values will be dp[2i][i] = true, the rest false, which means that there is always an empty path starting at any of the vertices.
Having the value true in dp[mask][last] we will make transitions forward, in the sense of "extending the path". That is, we will look for the numbers of vertices that are marked with zero in the mask (we have not yet visited them on the way) and at the same time such that there is an edge from last to this vertex (the path must be extended by an existing edge). That is, we do dp[mask | 2k][k] = true if dp[mask][last] = true AND mask & 2k = 0 (vertex k has not yet been visited) And there is an edge last -> k.
Ultimately, a Hamiltonian path exists if there is a true value in dp for the parameters of the all-ones bitmask and any last vertex.