CODEWITHSUNDEEP
javaalgorithmrecursion
anegru
anegru

Reputation: 1123

Find all paths from top left to bottom right problem. Recursive solution with array as parameter output explanation

I have an NxN matrix and I want to find all paths from top left corner to bottom right corner, provided that only down and right moves are allowed.

I built a class Point that holds coordinates within the matrix.


class Point
{
    public int x, y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString()
    {
        return "(" + this.x + "," + this.y + ")";
    }
}

The algorithm is recursive and checks all possible moves from each point.

public static void findPath(int grid[][], Point start, Point end, ArrayList<Point> currentPath)
{
        currentPath.add(start);

        if(start.x == end.x && start.y == end.y)
        {
            System.out.println(currentPath);
            return;
        }

        if(start.x + 1 < grid.length)
        {
            findPath(grid, new Point(start.x + 1, start.y), end, currentPath);
        }

        if(start.y + 1 < grid[0].length)
        {
            findPath(grid, new Point(start.x, start.y + 1), end, currentPath);
        }

}

For a simple 2x2 matrix i get the following output:

[(0,0), (1,0), (1,1)]
[(0,0), (1,0), (1,1), (0,1), (1,1)]

The expected output is:

[(0,0), (1,0), (1,1)]
[(0,0), (0,1), (1,1)]

It looks like after points (1,0), (1,1) are popped off the stack, the variable currentPath from the stack frame with the point (0,0), also contains the points (1,0), (1,1) from previous stack frames.

I am mainly interested in an explanation for this behaviour, since there are plenty of resources on the internet on solving the problem. Does it have to do with the fact that currentPath is allocated on the heap and only a pointer to that address is stored on the stack?

Thank you.

Upvotes: 1

Views: 457

Answers (1)

Eran
Eran

Reputation: 393811

There is only one ArrayList instance referenced by the currentPath local variable, so when you pass that variable to recursive calls, you are passing the same instance.

Since you are only adding elements to that ArrayList, any elements previously added will never be removed, so you see the points of both paths in your example.

You should remove from the ArrayList each point that you added once you are done with it, or you can pass a copy of the ArrayList to each recursive call:

public static void findPath(int grid[][], Point000 start, Point000 end, ArrayList<Point000> currentPath)
{
    currentPath.add(start);

    if(start.x == end.x && start.y == end.y)
    {
        System.out.println(currentPath);
        return;
    }

    if(start.x + 1 < grid.length)
    {
        findPath(grid, new Point000(start.x + 1, start.y), end, new ArrayList<>(currentPath));
    }

    if(start.y + 1 < grid[0].length)
    {
        findPath(grid, new Point000(start.x, start.y + 1), end, new ArrayList<>(currentPath));
    }

}

Now the output will be:

[(0,0), (1,0), (1,1)]
[(0,0), (0,1), (1,1)]

Upvotes: 2

Related Questions