# DFS Approach - Time Limit Exceeded - Perhaps a good start point

• This is a different approach to the DP and I get TLE. However as an initial attempt and a start point, it delivers.
The idea is to create a grid m * n and for each cell to be unique add a weight or a number to it by just counting to m * n. We then do a DFS to the end stop recursing row+1 and col +1 adding the weights we encounter in our path. If we reach the path, which is the bottom right, we store it in a set which ensures the path is unique. We simply add these paths up which is the total number of unique paths. As mentioned before it is suboptimal and I get TLE but points you in the right direction.

``````int uniqueHelper(int row, int col, vector<vector<int>>& grid, unordered_set<int>& visited, int weight)
{
if (row >= grid.size() || row < 0 || col >= grid[0].size() || col < 0) return 0;
if (row == grid.size() - 1 && col == grid[0].size() - 1) // if we reach the end see if our weight which is the sum of the path is in our set.
{
if (visited.find(weight) != visited.end()) return 0;
else
{
visited.emplace(weight);
return 1;
}
}
else
{
// Recurse and add the weights till we reach the end point which is the bottom right
return uniqueHelper(row + 1, col, grid, visited, weight + grid[row][col]) +
uniqueHelper(row, col + 1, grid, visited, weight + grid[row][col]);
}
}

// Recursive solution using DFS, suboptimal compared to DP solution
int uniquePaths(int m, int n) {
vector<vector<int>> grid(m, vector<int>(n));
unordered_set<int> visited;
for (int i = 0, weight = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j, ++weight)
{
//Set weights for each cell to uniquely identify a cell, [0,0] is [0,1] is 1 and so on
grid[i][j] = weight;
}
}

return uniqueHelper(0, 0, grid, visited,0);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.