Introduction
The first thing we need to make sure of before solving any DP with Bitmasking problem is that the constraints must be small because this approach takes exponential time and space.
Let us now discuss what is a Bitmask.
Bitmask is a Binary Number that stores some value inside it. Generally, we use Bitmask to memoize a recursive solution that represents the things we have already considered or visited.
Let us understand this with an example of the problem we will discuss further.
There is a salesman who wants to visit all the N cities once. Here the bitmask will be a Binary number and it will represent how many cities we have already visited when we are at a particular recursive call. The ith bit number which is set to 1 will represent that we have visited the ith city.
We maintain this Bitmask value and using this Bitmask value we try to memoize our recursive code.
Now, let us discuss the TSP problem.
We are given a 2D array of characters, including â€˜*â€™, â€˜.â€™, and â€˜#â€™.
â€˜*â€™ represents the Houses.
â€˜.â€™ represents an empty road.
â€˜#â€™ represents a blocked road.
We are currently at (0, 0) index and we need to visit all the houses only once and return back to our initial position (0, 0) at the end of the journey. We need to find the minimum distance to visit all the houses.
Approach
Our first step will be to calculate the shortest distance between the two houses. For this, we will run BFS from each house and find its minimum distance from each cell considering it as the source cell.
We will store the above result in a table of size O(Grid_size * N) (where â€˜Nâ€™ is the number of houses) so that we donâ€™t need to calculate it each time.
Now, we will try out all the combinations of traveling the houses and determine the minimum distance between them.
We will be using DP with Bitmasking to store the result for different states to reuse them.
Let us define the DP with Bitmasking state for the same.
DP[index][mask]: It will represent the minimum distance covered to reach the (index)th house after traveling all the houses stored in the mask. All the bits which are set to 1 in the mask are visited by us in the current state.
As soon as the mask has all the bits set to 1((1 << N)  1), that means we have visited all the cities and it is our answer.
At any state (index, mask), if all the bits are not set in the mask, we will visit the next house which is not already visited.
Hence the transition of DP with Bitmasking would look like as follows:
for(nxtHouse : off_bits_in_mask){ Dp[index][mask] = min(dp[index][mask], dp[nxtHouse][mask.set_bit(nxtHouse)] + dist[index][nxtHouse]); } 
Refer to the below implementation of the above approach.
#include <bits/stdc++.h>

Output
Time Complexity: There will be a maximum of N * (2 ^ N) states and for each state, we will be traversing all the N houses. Hence, the overall time complexity will be O(N ^ 2 * 2 ^ N).
Space Complexity: We are maintaining a DP table of size (N * 2 ^ N) which is a dominating term. Hence, the Space Complexity is O(N * 2^N).