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


  • 0
    S

    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);
        }

Log in to reply
 

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