Ran into this during my recent facebook onsite, it's similar to the 62. Unique Paths problem, but the guy wanted to enumerate all the paths (['DDRR', 'RDDR', 'DRDR'...]) and give the run-time of the solution, which he said was the main part of the question.

Instead of m * n grid, he simple said the map is a n * n square. I wrote the following backtracking code and give said the runtime is O(2^n). He said it's "good enough", but I'm pretty sure he was looking for a more specific answer. I've read up on the solutions of Unique Paths and realized the # of paths are C(m+n-2, m-1) so is the accurate runtime O(C(2n-2, n-1) * n) since each path is on the order of size n? I think this makes sense but cannot correlate it to my code. Anyways, please comment on my code here, and let me know if the runtime makes sense, or have u come up with a more specific runtime. Thanks!

    private void helper(int n, int i, int j, StringBuilder sb, List<String> paths) {
        if (i == n-1 && j == n-1) {
            paths.add(sb.toString());
            return;
        }
        if (i == n || j == n) return;
        int len = sb.length();
        sb.append('D');
        helper(n, i+1, j, sb, paths);
        sb.setLength(len);
        sb.append('R');
        helper(n, i, j+1, sb, paths);
        sb.setLength(len);
    }