Ninjas’ Vacation

The basic idea is to generate all permutations in which cities can be visited. For each permutation, we create a map to store the adjacent cities. If a city is not present in the map then the path will not be valid, else valid.

Example: 

Let a permutation be: 1 3 2 4

We create a map and insert the first element of permutation initially into it. Map : {1}

We now add all adjacent cities of 1 into the map, so the map becomes: {1, 2, 3, 4}

We move to the next element in the permutation, i.e., 3 which is present in the map and add its adjacent cities into the map. 

As all the cities are present in the map, so the permutation will be valid.
 

Now, let a permutation be: 1 4 3 2

Similarly, we will create a map and insert 1 into the map, so the map biomes: {1}

We will insert cities adjacent to 1 into the map, so the map now becomes: {1, 2, 3}

We move to the next element in the permutation, i.e., 4 which is not present in the map.

The permutation becomes invalid as 4 was not present in the map.
 

    We can do this for all the permutations to count the number of valid ways.
 

Here is the algorithm :

1. Create a graph (say, ‘GRAPH’) using the ‘CITIES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
2. Push the edges in the ‘GRAPH’.
3. Create an array (say, ‘ARR’) of size ‘N’ which will be used to store the permutations and initialize it from 0 to ‘N’.
4. Create a variable (say, ‘RES’) that will store the number of ways and initialize it with 0.
5. Call the ‘HELPER’ function which will generate all the permutations of array ‘ARR’.

HELPER(‘GRAPH’, ‘ARR’, ‘SI’, ‘EI, ‘RES’)
 

1. Base case:
   • If ‘SI’ is equal ‘EI’.
     1. Call the ‘CALC’ function which will check for the validity of the path and update the value of ‘RES’ by adding the result of the function.
2. Run a loop from ‘SI’ to ‘EI’ (say, iterator ‘i’) that will generate all the permutations of the array.
   • Swap ‘ARR[i]’ and ‘ARR[SI]’
   • Call the function recursively to generate other permutations.
   • Backtrack by again swapping ‘ARR[i]’ and ‘ARR[SI]’.
      

CALC(‘GRAPH’, ‘ARR’, ‘N’)

1. Create a map (say, ‘STORE’) that will store the adjacent cities and insert ‘ARR[0]’ into it.
2. Run a loop from 0 to ‘N’ (say, iterator ‘i’) to traverse the cities present in the array.
   • Check if ‘ARR[i]’ is not present in ‘STORE’.
     • Return 0.
   • Insert all the cities which are adjacent to ‘ARR[i]’ into the map.
3. Return 1.

Approach: In this approach, we will try to optimize the brute force approach with the help of  DP with Bitmasking. 

Bitmasking: If we want to represent a subset of a set with N elements, this subset can be encoded by a sequence of N bits. This sequence is called a bitmask. The basic idea is to use a bitmask where i-th bit will represent whether the i-th element has been included or not.

We will define DP[{MASK1, MASK2}], where MASK1 is a subset of total cities from where we can start the travel and MASK2 represents the cities available to visit. So, DP[MASK1][MASK2] will present the number of ways starting from cities in MASK1 we can travel the cities in MASK2.

As there are total ‘N ‘cities, MASK1 and MASK2 will be of N bits.
 

Algorithm:

1. Initialize an empty graph g with N vertices.
2. Maintain a variable ml with all N bits set.
3. Add edges to the graph. As the roads are bidirectional, add reverse edges as well.
4. Initialize a variable ans with value 0.
5. Iterate i in 0 to N
   1. ans += get(g, 1 << i, 0, dp).
   2. ans %= 1000000007.

     6. Finally, return ans.

GET(‘G’, ‘M1’, ‘M2’, ‘DP’)

1. If m2 is equal to ml. All cities are visited, which can be done in this way. So return 1.
2. If dp[{m1, m2}] is already computed return its value.
3. Otherwise,
   1. Initialize a variable ans with a value 0.
   2. Iterate i in 0 to N
      1. If i-th bit of mask m1 is set but i-th bit of mask m2 is unset.
         1. Set i-th bit of mask 'm2'
         2. Initialize a mask cc with value m1.
         3. Iterate j in g[i]
            1. cc |= (1 << j);
         4. ans += get(g, cc, m2, dp).
         5. ans %= 1000000007.
         6. Unset i-th bit of mask 'm2'
   3. Return dp[{m1, m2}] = ans.