299. Print All Possible Paths From Top Left to Bottom Right of a Matrix

Given the dimensions n and m of a grid with every cell open (no obstacles), print every distinct path from the top-left cell to the bottom-right cell that moves only right or down, one cell at a time. Represent each path as a string of moves ('D' for down, 'R' for right), and print every path on its own line, sorted alphabetically. If n = m = 1 (start and end are the same cell), print 'EMPTY'.

Input: The first line contains the integer n (number of rows). The second line contains the integer m (number of columns). Output: Print every distinct path as a string of 'D'/'R' moves, one per line, sorted alphabetically; print 'EMPTY' if n = m = 1.

1 <= n, m <= 6

The special case n=m=1 (start equals end) has no moves to make at all - the problem explicitly requires printing 'EMPTY' for this trivial case rather than an empty line.

Print every distinct path from a grid's top-left corner to its bottom-right corner, moving only right or down. Brute force: There isn't really a slower alternative distinct from this - the recursive path-building IS the direct approach; the only real choice is whether to try down-before-right or right-before-down first, which determines the output ORDER. Optimised: Building the path incrementally with a shared mutable string/list (append before recursing, pop after) avoids creating a brand new copy of the path at every single step - a lightweight backtracking technique that keeps memory overhead minimal even though the total NUMBER of paths is inherently exponential (combinatorial in grid size).

Recursively explore from the top-left cell, at each step trying to move right or down (when still in bounds), appending 'R' or 'D' to the path built so far via string concatenation, and recording a completed path once the bottom-right cell is reached. After all paths have been collected, sort the full list of path strings alphabetically before printing. This produces every path correctly, but creating a new string object at every single recursive step (since strings are immutable) adds unnecessary copying overhead, and sorting afterward is extra work that could potentially be avoided. Time: O(P * L log P) where P is the number of paths and L = n+m-2 Space: O(P * L)

Use the same recursive right/down exploration, but build the path in a single mutable buffer (such as a character array or StringBuilder) that is appended to on entering a cell and has its last character removed on backtracking out of it, rather than allocating a new string at every step. This keeps the per-step cost to O(1) amortized instead of O(L), and a full path is only ever materialized as a string once, at the moment it's complete. The final list is still sorted alphabetically afterward as a separate step. Time: O(P * L log P) Space: O(P * L)

Since 'D' comes before 'R' alphabetically, always try the down move before the right move at every branching point during the same backtracking traversal. Because every recursive call tries its two options in that fixed alphabetical order, and each complete path is emitted (printed or appended to the result list) at the moment it finishes, the paths naturally come out in sorted order with no extra comparison-based sort needed afterward at all. This removes the O(P log P) sorting factor entirely, leaving only the unavoidable work of generating and outputting every path. Time: O(P * L) Space: O(L) recursion stack plus O(P * L) for the collected output

1. Recurse from the current cell: if not in the last row, you may move down; if not in the last column, you may move right. 2. Append the chosen move's letter to the path, recurse into the resulting cell, then remove that letter (backtrack) before trying the sibling move. 3. Trying 'down' before 'right' at every step is exactly what produces paths already in alphabetical order.

Time: O(C(n+m-2, n-1) * (n+m)) - the number of paths is a binomial coefficient, and each path takes O(n+m) to construct/print. Space: O(n+m) for the recursion depth and current path being built, plus space for all generated path strings.

Test n = m = 1 (should print 'EMPTY') and the largest case n = m = 6 to confirm the number of paths stays manageable.

Be ready to connect this to the classic 'count paths in a grid' DP problem - this backtracking version does the same movement rules but ENUMERATES every path explicitly instead of just counting them.