在本教程中，我们将看到如何在MXN矩阵的左下角到右上角的所有路径。

问题

我们需要将所有路径从MXN矩阵的左下角打印。
我们可以向下移动或者向右移动。

解决方案

我们可以使用递归来解决此问题。

递归

• 我们将通过行和列来跟踪当前行和列。
• 路径将包含我们要打印的元素。
• 将当前元素添加到路径
• paths.add(矩阵[行] [列]);
• 通过更新行到行+ 1来下降
• MatrixPathHelper(列表，路径，矩阵，行+ 1，列);
• 通过更新列至列+ 1进行右转
• MatrixPathHelper(列表，路径，矩阵，行，列+ 1);
• 完成后，通过从列表中删除最后一个元素来回溯。
• paths.remove(paths.size() - 1);
• 基本情况1：
• 一旦我们到达最后一行，我们只能右转，因此从列中迭代到矩阵[0] .Length并将元素添加到路径。
• 基本情况2：
• 一旦我们到达最后一列，我们只能下降，因此将行迭代到矩阵.Length并向路径添加元素。

以下是完整的Java程序，用于将所有路径从MXN矩阵的左下角打印。

package org.igi.theitroad;
 
import java.util.ArrayList;
import java.util.List;
 
public class PrintMatrixPaths {
 
	public static void main(String[] args)
	{
		PrintMatrixPaths cmp=new PrintMatrixPaths();
		int[][] matrix= {
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
 
		
		List<List<Integer>> printMatrixPaths = cmp.printMatrixPaths(matrix);
		System.out.println("Paths: ");
		for(List<Integer> list:printMatrixPaths)
		{
			System.out.println(list);
		}
	}
 
	public List<List<Integer>> printMatrixPaths(int [][] matrix)
	{
		List<List<Integer>> list = new ArrayList<>();
		matrixPathsHelper(list, new ArrayList<Integer>(), matrix, 0,0);
		return list;
	}
 
	private void matrixPathsHelper(List<List<Integer>> list , List<Integer> paths, int [][] matrix, int row,int column){
 
		//base case
		if(row==matrix.length -1)
		{
			ArrayList<Integer> pathsTemp=new ArrayList<>(paths);
			for (int i = column; i < matrix[0].length; i++) {
				pathsTemp.add(matrix[row][i]);
			}
			list.add(pathsTemp);
			return;
		}
		
		//base case
		if(column==matrix[0].length -1)
		{
			ArrayList<Integer> pathsTemp=new ArrayList<>(paths);
			for (int i = row; i < matrix.length; i++) {
				pathsTemp.add(matrix[i][column]);
			}
			list.add(pathsTemp);
			return;
		}
		
		//Add to list
		paths.add(matrix[row][column]);
		
		//Explore
		//go down
		matrixPathsHelper(list, paths, matrix,row+1,column);
		
		//go right
		matrixPathsHelper(list, paths, matrix,row,column+1);
		
		//Remove from list : backtrack
		paths.remove(paths.size() - 1);
 
	}
}

输出

Paths:
[1, 4, 7, 8, 9]
[1, 4, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 2, 5, 6, 9]
[1, 2, 3, 6, 9]