java - Backtracking prorblem and I don't know if my plan to solve it is correct

Question

I am practicing a backtracking problem and here is the problem description: https://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/travel

Write a method travel that accepts integers x and y as parameters and uses recursive backtracking to print all solutions for traveling in the 2-D plane from (0, 0) to (x, y) by repeatedly using one of three moves:

East (E): move right 1 (increase x) North (N): move up 1 (increase y) Northeast (NE): move up 1 and right 1 (increase both x and y).

Here is what I got: I get it to work on one path but I am not sure how to make it go explore all other possible paths. I am thinking my base case design is wrong but I am not sure. I just want to know what I should fix first, is the base case or my entire concept is wrong.

public class PracticeRecordCode {
    public static void main(String[] args) {
        travel(1, 2);
    }
    public static String travel(int x, int y){
        List<String> allpath = new ArrayList<String>();

        String eachpath = "";

        return explore(0, 0, x, y, eachpath, allpath);
    }

    public static String explore(int x, int y, int des_x, int dest_y, String eachPath, List<String> allpath) {
        //Base case
        if(x == des_x && y== dest_y) {
                String result = "";
                if(isRepeated(eachPath, allpath)){
                    allpath.add(eachPath);
                    eachPath = "";
                }
            // Print all content from allpath
                for (String path : allpath) {
                    result += path + "
";
                    System.out.println(path);
                }
                return result;
        } else {

            if(x == des_x && y != dest_y){
                eachPath += "N ";
                if(!allpath.contains(eachPath)) {
                    allpath.add(eachPath);
                }
                explore(x, y+1, des_x, dest_y, eachPath, allpath);
            } else if(x != des_x && y == dest_y) {
                eachPath += "E ";
                allpath.add(eachPath);
                explore(x + 1, y, des_x, dest_y, eachPath, allpath);
            } else {
                eachPath += "NE ";
                allpath.add(eachPath);
                explore(x + 1, y+1, des_x, dest_y, eachPath, allpath);
            }
        }
        return "";
    }

    // Check if this path has been done already
    public static boolean isRepeated(String path, List<String> allpath){
        return allpath.contains(path);
    }

}

question from:https://stackoverflow.com/questions/65852397/backtracking-prorblem-and-i-dont-know-if-my-plan-to-solve-it-is-correct

Answer 1

we can do some improvements to your explore method, as there is some defect in your implementation. There are two exit conditions: 1. when you reach the destination, which is a valid path and we can save it into your final result. 2. you reach over the destination (x>des_x || y>dest_y), which means that's an invalid path, and we don't have to keep exploring any more. And otherwise, you have 3 options to keep exploring: E, N, or NE. And as each direction is unique, you don't have to worry about duplicate. when all possible explore is done, your allpath list will have all the valid paths added. And you can either return the list or print it. Based on this, your code can be much simpler like this:

import java.util.ArrayList;
import java.util.List;

public class PracticeRecordCode {

    public static void main(String[] args) {
        travel(2, 2);
    }
    public static void travel(int x, int y){
        List<String> allpath = new ArrayList<String>();

        explore(0, 0, x, y, "", allpath);

        // Print all content from allpath
        for (String path : allpath) {
            System.out.println(path);
        }

    }

    public static void explore(int x, int y, int des_x, int dest_y, String eachPath, List<String> allpath) {
        //Base case
        if(x == des_x && y == dest_y) {
            allpath.add(eachPath);
            return;
        }
        if(x>des_x || y>dest_y)
            return;
        explore(x + 1, y, des_x, dest_y, eachPath + "E ", allpath);

        explore(x, y+1, des_x, dest_y, eachPath + "N ", allpath);

        explore(x + 1, y+1, des_x, dest_y, eachPath + "NE ", allpath);
    }
}